×

Acyclic vertex coloring of graphs of maximum degree six. (English) Zbl 1288.05107

Summary: In this paper, we prove that every graph with maximum degree six is acyclically 10-colorable, thus improving the main result of H. Hocquard [Inf. Process. Lett. 111, No. 15, 748–753 (2011; Zbl 1260.05059)].

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory

Citations:

Zbl 1260.05059
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Berman, D. M., Every planar graph has an acyclic 7-coloring, Israel J. Math., 28, 169-174 (1977) · Zbl 0374.05022
[2] Alon, N.; McDiarmid, C.; Reed, B., Acyclic coloring of graphs, Random Structures Algorithms, 2, 3, 277-288 (1991) · Zbl 0735.05036
[3] Bollobás, Béla, Modern Graph Theory (1998), Springer-Verlag, New York, Inc. · Zbl 0902.05016
[4] Borodin, O. V., On acyclic colorings of planar graphs, Discrete Math., 25, 211-236 (1979) · Zbl 0406.05031
[5] Burstein, M. I., Every 4-valent graph has an acyclic 5-coloring, Soob.S.C. Akad. Nauk Gruzin. SSR, 93, 21-24 (1979), (in Russian) · Zbl 0397.05023
[6] Fertin, G.; Godard, E.; Raspaud, A., Acyclic and \(k\)-distance coloring of the grid, Inform. Process. Lett., 87, 1, 51-58 (2003) · Zbl 1175.68293
[7] Fertin, G.; Godard, E.; Raspaud, A., Minimum feedback vertex set and acyclic coloring, Inform. Process. Lett., 84, 131-139 (2002) · Zbl 1042.68090
[8] Fertin, G.; Raspaud, A., Acyclic coloring of graphs of maximum degree five: nine colors are enough, Inform. Process. Lett., 105, 65-72 (2008) · Zbl 1183.05027
[9] Fiedorowicz, A., Acyclic 6-coloring of graphs with maximum degree 5 and small maximum average degree, Discuss. Math. Graph Theory, 33, 91-99 (2013) · Zbl 1291.05061
[10] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. Math., 14, 3, 390-408 (1973) · Zbl 0265.05103
[11] Hocquard, Hervé, Graphs with maximum degree 6 are acyclically 11-colorable, Inform. Process. Lett., 111, 748-753 (2011) · Zbl 1260.05059
[12] Kostochka, A. V., Acyclic 6-colorings of planar graphs, Metody Diskret. Anal., 28, 40-56 (1976), (in Russian) · Zbl 0412.05043
[13] Kostochka, A. V.; Stocker, C., Graphs with maximum degree 5 are acyclically 7-colorable, Ars Math. Contemp., 4, 153-164 (2011) · Zbl 1236.05083
[14] Mitchem, J., Every planar graph has an acyclic 8-coloring, Duke Math. J., 41, 177-181 (1974) · Zbl 0284.05103
[15] Skulrattanakulchai, S., Acyclic colorings of subcubic graphs, Inform. Process. Lett., 92, 161-167 (2004) · Zbl 1169.05325
[16] S˘pacapan, S.; Tepeh, A., On acyclic colorings of direct products, Discuss. Math. Graph Theory, 28, 323-333 (2008) · Zbl 1156.05018
[17] West, D., Introduction to Graph Theory (2001), Prentice-Hall
[18] Yadav, K.; Varagani, S.; Kothapalli, K.; Venkaiah, V. Ch., Acyclic vertex coloring of graphs of maximum degree 6, Electron. Notes Discrete Math., 35, 177-182 (2009) · Zbl 1268.05086
[19] Yadav, K.; Varagani, S.; Kothapalli, K.; Venkaiah, V. Ch., Acyclic vertex coloring of graphs of maximum degree 5, Discrete Math., 311, 342-348 (2011) · Zbl 1222.05077
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.