zbMATH — the first resource for mathematics

\((k,j)\)-coloring of sparse graphs. (English) Zbl 1239.05059
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_{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 \(j\). In this paper, we give a sufficient condition of (\(k,j\))-colorability for graphs with bounded maximum average degree.

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
90C05 Linear programming
05C35 Extremal problems in graph theory
05C07 Vertex degrees
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 2-coloring the vertices of sparse graphs, Discrete anal. oper. res., 16, 2, 16-20, (2009) · Zbl 1249.05110
[4] 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
[5] O.V. Borodin, A.O. Ivanova, M. Montassier, A. Raspaud, \((k, 1)\)-coloring of sparse graphs, Manuscript, 2009. · Zbl 1238.05084
[6] 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
[7] Dantzig, G.B.; Thapa, M.N., ()
[8] Eaton, N.; Hull, T., Defective List colorings of planar graphs, Bull. inst. combin. appl., 25, 79-87, (1999) · Zbl 0916.05026
[9] Glebov, A.N.; Zambalaeva, D.Zh., Path partitions of planar graphs, Sib. electr. math. rep., 4, 450-459, (2007), (in Russian) http://semr.math.nsc.ru · 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
[11] Khachiyan, L.G., A polynomial algorithm in linear programming, Dokl. akad. nauk SSSR, 224, 1093-1096, (1979), (English Translation: Sov. Math. Dokl., 20, 1979, 191-194) · Zbl 0414.90086
[12] ┼á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.