zbMATH — the first resource for mathematics

On 1-improper 2-coloring of sparse graphs. (English) Zbl 1281.05060
Summary: A graph \(G\) is \((1,1)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that every vertex in \(G[V_i]\) has degree at most 1 for each \(i\in\{1,2\}\). We prove that every graph with maximum average degree at most \(\frac{14}{5}\) is \((1,1)\)-colorable. In particular, it follows that every planar graph with girth at least 7 is (\(1,1\))-colorable. On the other hand, we construct graphs with maximum average degree arbitrarily close to \(\frac{14}{5}\) (from above) that are not \((1,1)\)-colorable.
In fact, we establish the best possible sufficient condition for the \((1,1)\)-colorability of a graph \(G\) in terms of the minimum, \(\rho_G\), of \(\rho_G(S)=7| S| -5| E(G[S])|\) over all subsets \(S\) of \(V(G)\). Namely, every graph \(G\) with \(\rho_G\geq 0\) is \((1,1)\)-colorable. On the other hand, we construct infinitely many non-\((1,1)\)-colorable graphs \(G\) with \(\rho_G=-1\). This solves a related conjecture of A. Kurek and A. Ruciński from [J. Graph Theory 18, No. 1, 73–81 (1994; Zbl 0790.05027)].

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
Full Text: DOI
[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 vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper., 16, 2, 16-20, (2009), (in Russian). Translated in: Journal of Applied and Industrial Mathematics 4 (1) (2010) 21-23 · Zbl 1249.05110
[4] Borodin, O. V.; Ivanova, A. O., List strong linear 2-arboricity of sparse graphs, J. Graph Theory, 67, 2, 83-90, (2011) · Zbl 1218.05038
[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, 1)\)-coloring of sparse graphs, Discrete Math., 312, 6, 1128-1135, (2012) · Zbl 1238.05084
[7] 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
[8] Borodin, O. V.; Kostochka, A. V., On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density, J. Comb. Theory B, 23, 247-250, (1977) · Zbl 0336.05104
[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). Translation in: Siberian Mathematical Journal 52 (5) 796-801 · Zbl 1232.05073
[10] O.V. Borodin, A.V. Kostochka, Defective 2-colorings of sparse graphs, submitted for publication. · Zbl 1282.05041
[11] 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
[12] Erdős, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157, (1979)
[13] Gerencsér, L., Szinezesi problemacrol, Mat. Lapok, 16, 274-277, (1965)
[14] Glebov, A. N.; Zambalaeva, D. Zh., Path partitions of planar graphs, Sib. Elektron. Mat. Izv., 4, 450-459, (2007), (in Russian) · Zbl 1132.05315
[15] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 181-199, (2006) · Zbl 1104.05026
[16] Kurek, A.; Ruciński, A., Globally sparse vertex-Ramsey graphs, J. Graph Theory, 18, 1, 73-81, (1994) · Zbl 0790.05027
[17] Lovász, L., On decomposition of graphs, Studia Sci. Math. Hungar, 1, 237-238, (1966) · Zbl 0151.33401
[18] Mihók, P., On vertex partition numbers of graphs, (Graphs and Other Combinatorial Topics (Prague, 1982), Teubner-Texte Math., vol. 59, (1983), Teubner Leipzig), 183-188
[19] Vizing, V. G., Vertex colourings with given colours, Metody Discret. Analiz, 29, 3-10, (1976), (in Russian)
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.