×

zbMATH — the first resource for mathematics

\((k,1)\)-coloring of sparse graphs. (English) Zbl 1238.05084
Summary: A graph \(G\) is \((k,1)\)-colorable if the vertex set of \(G\) can be partitioned into subsets \(V_{1}\) and \(V_{2}\) such that the graph \(G[V_{1}]\) induced by the vertices of \(V_{1}\) has maximum degree at most \(k\) and the graph \(G[V_{2}]\) induced by the vertices of \(V_{2}\) has maximum degree at most 1. We prove that every graph with maximum average degree less than \(\frac {10k+22}{3k+9}\) admits a \((k,1)\)-coloring, where \(k\geq 2\). In particular, every planar graph with girth at least 7 is (2,1)-colorable, while every planar graph with girth at least 6 is (5,1)-colorable. On the other hand, when \(k\geq 2\) we construct non-\((k,1)\)-colorable graphs whose maximum average degree is arbitrarily close to \(\frac {14k}{4k+1}\).

MSC:
05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, K.; Haken, W., Every planar map is four colorable. part I. discharging, Illinois J. math., 21, 429-490, (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W., Every planar map is four colorable. part II. reducibility, Illinois J. math., 21, 491-567, (1977) · Zbl 0387.05010
[3] Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[4] Borodin, O.V.; Hartke, S.G.; Ivanova, A.O.; Kostochka, A.V.; West, D.B., (5, 2)-coloring of sparse graphs, Sib. elektron. mat. izv., 5, 417-426, (2008) · Zbl 1299.05115
[5] Borodin, O.V.; Ivanova, A.O., Near proper 2-coloring the vertices of sparse graphs, Diskretn. anal. issled. oper., 16, 2, 16-20, (2009) · Zbl 1249.05110
[6] Borodin, O.V.; Ivanova, A.O.; Kostochka, A.V., Oriented vertex 5-coloring of sparse graphs, Diskretn. anal. issled. oper., 13, 1, 16-32, (2006), (in Russian) · Zbl 1249.05112
[7] Borodin, O.V.; Ivanova, A.O.; Montassier, M.; Ochem, P.; Raspaud, A., Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\), J. graph theory, 65, 2, 83-93, (2010) · Zbl 1209.05177
[8] Borodin, O.V.; Ivanova, A.O.; Neustroeva, T.K., List 2-distance \((\Delta + 1)\)-coloring of planar graphs with given girth, Diskretn. anal. issled. oper., 14, 3, 13-30, (2007), (in Russian) · Zbl 1249.05114
[9] Borodin, O.V.; Kostochka, A.V., Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one, Sibirsk. mat. zh., 52, 5, 1004-1010, (2011), (in Russian) · Zbl 1232.05073
[10] Cowen, L.J.; Cowen, R.H.; Woodall, D.R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. graph theory, 10, 2, 187-195, (1986) · Zbl 0596.05024
[11] Eaton, N.; Hull, T., Defective List colorings of planar graphs, Bull. inst. combin. appl., 25, 79-87, (1999) · Zbl 0916.05026
[12] Glebov, A.N.; Zambalaeva, D.Zh., Path partitions of planar graphs, Sib. elektron. mat. izv., 4, 450-459, (2007), http://semr.math.nsc.ru (in Russian) · Zbl 1132.05315
[13] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. graph theory, 52, 181-199, (2006) · Zbl 1104.05026
[14] ┼ákrekovski, R., List improper coloring of planar graphs, Combin. probab. comput., 8, 293-299, (1999) · Zbl 0940.05031
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.