Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency.

*(English)*Zbl 0596.05024A graph is called (m,k)-colorable if its vertices can be colored with m colors such that each vertex is adjacent to at most k vertices of the same color as itself. Also (a,b)\(\geq (c,d)\) means \(a\geq c\) and \(b\geq d\). Theorem A. Every outer-planar graph is (m,k)-colorable iff (m,k)\(\geq (2,2)\) or (3,0). Theorem B. Every planar graph is (m,k)-colorable iff (m,k)\(\geq (4,0)\) or (3,2). Theorem C. For each compact surface s, there is an integer k such that every graph embedded in s can be (4,k)-colored. Conjecture. In Theorem C, 3 can replace 4. Conjecture. If G is planar, then V(G) can be partitioned into subsets \(V_ 1\), \(V_ 2\), \(V_ 3\) such that each \(v_ i\) induces a union of disjoint paths and each \(V_ i\cup V_ j\) induces an outerplanar graph.

Reviewer: J.Mitchem

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

PDF
BibTeX
XML
Cite

\textit{L. J. Cowen} et al., J. Graph Theory 10, No. 2, 187--195 (1986; Zbl 0596.05024)

Full Text:
DOI

##### References:

[1] | Appel, Illinois J. Math. 20 pp 218– (1976) |

[2] | Graph Theory. Addison-Wesley, Reading, MA (1969). |

[3] | LovĂˇsz, Studia Sci. Math. Hungar. 1 pp 237– (1966) |

[4] | and , The Appel-Haken proof of the four-color theorem. Selected Topics in Graph Theory, and , Eds. Academic, London (1978), pp. 83–101. |

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.