×

zbMATH — the first resource for mathematics

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\). (English) Zbl 1209.05177
Summary: A graph \(G\) is \((k,0)\)-colorable if its vertices can be partitioned into subsets \(V_{1}\) and \(V_{2}\) such that in \(G[V_{1}]\) every vertex has degree at most \(k\), while \(G[V_{2}]\) is edgeless. For every integer \(k \geq 0\), we prove that every graph with the maximum average degree smaller than \((3k+4)/(k+2)\) is \((k,0)\)-colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)-colorable. On the other hand, we construct planar graphs with girth 6 that are not \((k,0)\)-colorable for arbitrarily large \(k\).

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, Every planar map is four colorable. Part I. Discharging, Illinois J Math 21 pp 429– (1977) · Zbl 0387.05009
[2] Appel, Every planar map is four colorable. Part II. Reducibility, Illinois J Math 21 pp 491– (1977) · Zbl 0387.05010
[3] Borodin, On the total coloring of planar graphs, J Reine Angew Math 394 pp 180– (1989) · Zbl 0653.05029
[4] Borodin, Sufficient conditions for planar graphs with girth 6 to be 2-distance colourable, Sib Elektron Mat Izv 3 pp 441– (2006)
[5] Borodin, (5,2)-coloring of sparse graphs, Sib Elektron Mat Izv 5 pp 417– (2008)
[6] Borodin, Near-proper list vertex 2-colorings of sparse graphs, Diskret Anal Issled Oper 16 (2) pp 16– (2009) · Zbl 1249.05110
[7] Borodin, Oriented vertex 5-coloring of sparse graphs, Diskret Anal Issled Oper 13 (1) pp 16– (2006) · Zbl 1249.05112
[8] Borodin, Homomorphisms of sparse graphs with large girth, J Combin Theory B 90 pp 147– (2004) · Zbl 1033.05037
[9] Borodin, List edge and list total colourings of multigraphs, J Combin Theory B 71 (2) pp 184– (1997) · Zbl 0876.05032
[10] Borodin, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math 206 pp 77– (1999) · Zbl 0932.05033
[11] Eaton, Defective list colorings of planar graphs, Bull Inst Combin Appl 25 pp 79– (1999) · Zbl 0916.05026
[12] Glebov, Path partitions of planar graphs, Sib Elektron Mat Izv 4 pp 450– (2007) · Zbl 1132.05315
[13] He, Edge-partitions of planar graphs and their game coloring numbers, J Graph Theory 41 pp 307– (2002) · Zbl 1016.05033
[14] Havet, Improper choosability of graphs and maximum average degree, J Graph Theory 52 pp 181– (2006) · Zbl 1104.05026
[15] ┼ákrekovski, List improper coloring of planar graphs, Combin Probab Comput 8 pp 293– (1999) · Zbl 0940.05031
[16] Wang, Edge-partitions of graphs of nonnegative characteristic and their game coloring number, Discrete Math 2 pp 262– (2006) · Zbl 1086.05035
[17] Wu, On the linear arboricity of planar graphs of nonnegative characteristic and their game coloring number, J Graph Theory 31 pp 129– (1999)
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.