zbMATH — the first resource for mathematics

Defective 2-colorings of sparse graphs. (English) Zbl 1282.05041
Summary: A graph $$G$$ is $$(j,k)$$-colorable if its vertices can be partitioned into subsets $$V_1$$ and $$V_2$$ such that every vertex in $$G[V_1]$$ has degree at most $$j$$ and every vertex in $$G[V_2]$$ has degree at most $$k$$. We prove that if $$k\geqslant 2j+2$$, then every graph with maximum average degree at most $$2\left(2-\frac{k+2}{(j+2)(k+1)}\right)$$ is $$(j,k)$$-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close to $$2\left(2-\frac{k+2}{(j+2)(k+1)}\right)$$ (from above) that are not $$(j,k)$$-colorable.In fact, we prove a stronger result by establishing the best possible sufficient condition for the $$(j,k)$$-colorability of a graph $$G$$ in terms of the minimum, $$\phi_{j,k}(G)$$, of the difference $$\phi_{j,k}(W,G)=\left(2-\frac{k+2}{(j+2)(k+1)}\right)| W| -| E(G[W])|$$ over all subsets $$W$$ of $$V(G)$$. Namely, every graph $$G$$ with $$\phi_{j,k}(G)>\frac{-1}{k+1}$$ is $$(j,k)$$-colorable. On the other hand, we construct infinitely many non-$$(j,k)$$-colorable graphs $$G$$ with $$\phi_{j,k}(G)=\frac{-1}{k+1}$$.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C42 Density (toughness, etc.) 05C35 Extremal problems in graph theory 05C07 Vertex degrees
Full Text:
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.; Ivanova, A. O., Near-proper List vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper., J. Appl. Ind. Math., 4, 1, 21-23, (2010), (in Russian); English translation in: [4] 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., Sib. Math. J., 52, 5, 796-801, (2011), (in Russian); translation in: · Zbl 1232.05073 [5] 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, 83-93, (2010) · Zbl 1209.05177 [6] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Raspaud, A., $$(k, j)$$-coloring of sparse graphs, Discrete Appl. Math., 159, 17, 1947-1953, (2011) · Zbl 1239.05059 [7] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Raspaud, A., $$(k, 1)$$-coloring of sparse graphs, Discrete Math., 312, 6, 1128-1135, (2012) · Zbl 1238.05084 [8] 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, 187-195, (1986) · Zbl 0596.05024 [9] Glebov, A. N.; Zambalaeva, D. Zh., Path partitions of planar graphs, Sib. Elektron. Mat. Izv., 4, 450-459, (2007), (in Russian) · Zbl 1132.05315 [10] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 181-199, (2006) · Zbl 1104.05026
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.