zbMATH — the first resource for mathematics

Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. (English) Zbl 0596.05024
A 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

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[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.