Abstract | ||
---|---|---|
A graph is (k1,k2)-colorable if it admits a vertex partition into a graph with maximum degree at most k1 and a graph with maximum degree at most k2. We show that every (C3,C4,C6)-free planar graph is (0,6)-colorable. We also show that deciding whether a (C3,C4,C6)-free planar graph is (0,3)-colorable is NP-complete. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2019.07.002 | Discrete Mathematics |
Keywords | DocType | Volume |
Improper colorings,Planar graphs | Journal | 342 |
Issue | ISSN | Citations |
11 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
François Dross | 1 | 10 | 5.83 |
Pascal Ochem | 2 | 258 | 36.91 |