zbMATH — the first resource for mathematics

Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs. (English) Zbl 1419.05053
Summary: A graph is \((k_1, k_2)\)-colorable if it admits a vertex partition into a graph with maximum degree at most \(k_1\) and a graph with maximum degree at most \(k_2\). We show that every \((C_3, C_4, C_6)\)-free planar graph is \((0, 6)\)-colorable. We also show that deciding whether a \((C_3, C_4, C_6)\)-free planar graph is \((0, 3)\)-colorable is NP-complete.
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory S. B, 104, 72-80, (2014) · Zbl 1282.05041
[2] Choi, I.; Liu, C.-H.; Oum, S., Characterization of cycle obstruction sets for improper coloring planar graphs, SIAM J. Discrete Math., 32, 2, 1209-1228, (2018) · Zbl 1388.05061
[3] Esperet, L.; Montassier, M.; Ochem, P.; Pinlou, A., A complexity dichotomy for the coloring of sparse graphs, J. Graph Theory, 73, 1, 85-102, (2013) · Zbl 1264.05049
[4] Kim, J.; Kostochka, A. V.; Zhu, X., Improper coloring of sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs, European J. Combin., 42, 26-48, (2014) · Zbl 1297.05083
[5] Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1, (2015), #P157 · Zbl 1308.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.