×

zbMATH — the first resource for mathematics

\((1,k)\)-coloring of graphs with girth at least five on a surface. (English) Zbl 1359.05099
Summary: A graph is \((d_1\ldots,d_r)\)-colorable if its vertex set can be partitioned into \(r\) sets \(V_1,\ldots,V_r\) so that the maximum degree of the graph induced by \(V_i\) is at most \(d_i\) for each \(i\in\{1,\ldots,r\}\). For a given pair \((g,d_1)\), the question of determining the minimum \(d_2=d_2(g,d_1)\) such that planar graphs with girth at least \(g\) are \((d_1,d_2)\)-colorable has attracted much interest. The finiteness of \(d_2(g,d_1)\) was known for all cases except when \((g,d_1)=(5,1)\). M. Montassier and P. Ochem [Electron. J. Comb. 22, No. 1, Research Paper P1.57, 13 p. (2015; Zbl 1308.05052)] explicitly asked if \(d_2(5,1)\) is finite. We answer this question in the affirmative with \(d_2(5,1)\leq10\); namely, we prove that all planar graphs with girth at least five are \((1,10)\)-colorable. Moreover, our proof extends to the statement that for any surface \(S\) of Euler genus \(\gamma\), there exists a \(K=K(\gamma)\) where graphs with girth at least five that are embeddable on \(S\) are \((1,K)\)-colorable. On the other hand, there is no finite \(k\) where planar graphs (and thus embeddable on any surface) with girth at least five are \((0,k)\)-colorable.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, Every planar map is four colorable. I. Discharging, Illinois J Math 21 (3) pp 429– (1977) · Zbl 0387.05009
[2] Appel, Every planar map is four colorable. II. Reducibility, Illinois J Math 21 (3) pp 491– (1977) · Zbl 0387.05010
[3] Borodin, Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, J Graph Theory 65 (2) pp 83– (2010) · Zbl 1209.05177 · doi:10.1002/jgt.20467
[4] Borodin, (k,j)-coloring of sparse graphs, Discrete Appl Math 159 (17) pp 1947– (2011) · Zbl 1239.05059 · doi:10.1016/j.dam.2011.06.021
[5] Borodin, (k, 1)-coloring of sparse graphs, Discrete Math 312 (6) pp 1128– (2012) · Zbl 1238.05084 · doi:10.1016/j.disc.2011.11.031
[6] Borodin, On 1-improper 2-coloring of sparse graphs, Discrete Math 313 (22) pp 2638– (2013) · Zbl 1281.05060 · doi:10.1016/j.disc.2013.07.014
[7] Borodin, Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1, Sibirsk Mat Zh 52 (5) pp 1004– (2011) · Zbl 1232.05073
[8] Borodin, Defective 2-colorings of sparse graphs, J Combin Theory Ser B 104 pp 72– (2014) · Zbl 1282.05041 · doi:10.1016/j.jctb.2013.10.002
[9] Borodin, Near proper 2-coloring the vertices of sparse graphs, Diskretn Anal Issled Oper 16 (2) pp 16– (2009)
[10] I. Choi A. Raspaud Planar graphs with minimum cycle length at least 5 are (3, 5)-colorable 338 2015
[11] Cowen, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J Graph Theory 10 (2) pp 187– (1986) · Zbl 0596.05024 · doi:10.1002/jgt.3190100207
[12] Eaton, Defective list colorings of planar graphs, Bull Inst Combin Appl 25 pp 79– (1999) · Zbl 0916.05026
[13] Esperet, A complexity dichotomy for the coloring of sparse graphs, J Graph Theory 73 (1) pp 85– (2013) · Zbl 1264.05049 · doi:10.1002/jgt.21659
[14] Glebov, Path partitions of planar graphs, Sib Èlektron Mat Izv 4 pp 450– (2007) · Zbl 1132.05315
[15] Havet, Improper choosability of graphs and maximum average degree, J Graph Theory 52 (3) pp 181– (2006) · Zbl 1104.05026 · doi:10.1002/jgt.20155
[16] J. Kim A. V. Kostochka X. Zhu Private communication 2013
[17] Montassier, Near-colorings: non-colorable graphs and NP-completeness, Electron J Combin 22 (1) (2015) · Zbl 1308.05052
[18] Škrekovski, List improper colourings of planar graphs, Combin Probab Comput 8 (3) pp 293– (1999) · Zbl 0940.05031 · doi:10.1017/S0963548399003752
[19] Škrekovski, List improper colorings of planar graphs with prescribed girth, Discrete Math 214 (1-3) pp 221– (2000) · Zbl 0940.05027 · doi:10.1016/S0012-365X(99)00145-4
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.