×

zbMATH — the first resource for mathematics

List strong linear 2-arboricity of sparse graphs. (English) Zbl 1218.05038
Summary: A graph \(G\) is called \((k, j)\)-colorable if the vertex set of \(G\) can be partitioned into subsets \(V_{1}\) and \(V_{2}\) such that the graph \(G[V_{i}]\) induced by the vertices of \(V_{i}\) has maximum degree at most \(k\) for \(i = 1\) and at most \(j\) for \(i = 2\). In particular, F. Havet and J.-S. Sereni [J. Graph Theory 52, No. 3, 181–199 (2006; Zbl 1104.05026)] proved that each planar graph \(G\) is list \((1, 1)\)-colorable if its girth, \(g(G)\), is at least 8 and list \((2, 2)\)-colorable if \(g(G) \geq 6\). O. V. Borodin and A. O. Ivanova [Diskretn. Anal. Issled. Oper., Ser. 1 16, No 2, 16–20(2009)] proved that every planar graph is \((2, 1)\)-colorable if \(g(G) \geq 7\) and \((5, 1)\)-colorable if \(g(G) \geq 6\). In fact, all these results were proved for each not necessarily planar sparse graph \(G\), i.e., having a low maximum average degree, \(\text{mad}(G)\), over all subgraphs.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, Variable degeneracy: Extensions of Brooks’ and Gallai’s theorems, Discrete Math 214 pp 101– (2000) · Zbl 0949.05029 · doi:10.1016/S0012-365X(99)00221-6
[2] Borodin, Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable, J Graph Theory 62 (3) pp 234– (2009) · Zbl 1180.05035 · doi:10.1002/jgt.20394
[3] Borodin, Near-proper vertex 2-colorings of sparse graphs, Diskretn Anal Issled Oper 16 (2) pp 16– (2009) · Zbl 1249.05110
[4] O. V. Borodin A. O. Ivanova M. Montassier A. Raspaud ( k , 1)-coloring of sparse graphs (submitted) · Zbl 1238.05084
[5] Borodin, Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, J Graph Theory (2009) · Zbl 1209.05177
[6] Borodin, Oriented 7-coloring of plane graphs with girth at least 7, Sib Elektron Mat Izv 2 pp 222– (2005) · Zbl 1095.05013
[7] O. V. Borodin M. Chen A. O. Ivanova A. Raspaud Acyclic 3-choosability of sparse graphs with girth at least 7 · Zbl 1213.05049
[8] Chartrand, The point arboricity of planar graphs, J London Math Soc 44 pp 612– (1969) · Zbl 0175.50505 · doi:10.1112/jlms/s1-44.1.612
[9] Cowen, Defective list colorings of graphs in surfaces: Partitions into subgraphs of bounded valency, J Graph Theory 10 pp 187– (1986) · Zbl 0596.05024 · doi:10.1002/jgt.3190100207
[10] Glebov, Path partitions of planar graphs, Sib Elektron Mat Izv 4 pp 450– (2007) · Zbl 1132.05315
[11] Eaton, Defective list colorings of planar graphs, Bull Inst Combin Appl 25 pp 79– (1999) · Zbl 0916.05026
[12] Erdos, Choosability in graphs, Congr Numer 26 pp 125– (1979)
[13] Havet, Improper choosability of graphs and maximum average degree, J Graph Theory 52 pp 181– (2006) · Zbl 1104.05026 · doi:10.1002/jgt.20155
[14] Raspaud, On the vertex-arboricity of planar graphs, European J Combin 29 (4) pp 1064– (2008) · Zbl 1144.05024 · doi:10.1016/j.ejc.2007.11.022
[15] Poh, On the linear vertex-arboricity of a planar graph, J Graph Theory 14 (1) pp 73– (1990) · Zbl 0705.05016 · doi:10.1002/jgt.3190140108
[16] Škrekovski, List improper coloring of planar graphs, Comb Prob Comp 8 pp 293– (1999) · Zbl 0940.05031 · doi:10.1017/S0963548399003752
[17] Škrekovski, List improper colorings of planar graphs with prescribed girth, Discrete Math 214 pp 221– (2000) · Zbl 0940.05027 · doi:10.1016/S0012-365X(99)00145-4
[18] Vizing, Vertex colourings with given colours, Metody Discret Analiz 29 pp 3– (1976)
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.