zbMATH — the first resource for mathematics

Degenerate and star colorings of graphs on surfaces. (English) Zbl 1230.05133
Summary: We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of G. Fertin, A. Raspaud, and B. Reed [J. Graph Theory 47, No. 3, 163–182 (2004; Zbl 1055.05051)]: If \(G\) is a graph of maximum degree \(\Delta \), then \(G\) admits a degenerate star coloring using \(O(\Delta ^{3/2})\) colors. We use this result to prove that every graph of genus \(g\) admits a degenerate star coloring with \(O(g^{3/5})\) colors. It is also shown that these results are sharp up to a logarithmic factor.

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Zbl 1055.05051
Full Text: DOI
[1] Albertson, M.O.; Chappell, G.G.; Kierstead, H.A.; Kündgen, A.; Ramamurthi, R., Coloring with no 2-colored \(P_4\)’s, Electron. J. combin., 11, 13, (2004) · Zbl 1053.05045
[2] Alon, N.; McDiarmid, C.; Reed, B., Acyclic colouring of graphs, Random structures algorithms, 2, 277-288, (1991) · Zbl 0735.05036
[3] Alon, N.; Mohar, B.; Sanders, D.P., On acyclic colorings of graphs on surfaces, Israel J. math., 94, 273-283, (1996) · Zbl 0857.05033
[4] Alon, N.; Spencer, J.H., The probabilistic method, (2000), Wiley New York
[5] Borodin, O.V., On decomposition of graphs into degenerate subgraphs in Russian, Diskret. analiz., 28, 3-12, (1976) · Zbl 0425.05058
[6] Borodin, O.V., A proof of grünbaum’s conjecture on the acyclic 5-colorability of planar graphs, Sov. math. dokl., 17, 1499-1502, (1976) · Zbl 0363.05031
[7] Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 211-236, (1979) · Zbl 0406.05031
[8] Fertin, G.; Raspaud, A.; Reed, B., Star coloring of graphs, J. graph theory., 47, 163-182, (2004) · Zbl 1055.05051
[9] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 14, 390-412, (1973) · Zbl 0265.05103
[10] Kierstead, H.A.; Mohar, B.; Špacapan, S.; Yang, D.; Zhu, X., The two-coloring number and degenerate colorings of planar graphs, SIAM J. discrete math., 23, 1548-1560, (2009) · Zbl 1207.05058
[11] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore · Zbl 0979.05002
[12] Molloy, M.; Reed, B., Graph colouring and the probabilistic method, (2002), Springer · Zbl 0987.05002
[13] Nešetřil, J.; Ossona de Mendez, P., (), 651-664
[14] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion I. decompositions, Europ. J. combinatorics., 29, 760-776, (2008) · Zbl 1156.05056
[15] Nešetřil, J.; Ossona de Mendez, P., From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits, European congress of mathematics, Eur. math. soc., 135-165, (2010), Zürich · Zbl 1196.05080
[16] Rautenbach, D., A conjecture of borodin and a coloring of grünbaum, J. graph theory., 58, 139-147, (2008) · Zbl 1154.05035
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.