×

On chromatic numbers of two extensions of planar graphs. (English) Zbl 1417.05079

Summary: In this paper, the acyclic chromatic and the circular list chromatic numbers of a simple \(H\)-minor free graph \(G\) is considered, where \(H\in \{K_5,K_{3,3}\}\). It is proved that the acyclic chromatic number (resp. the circular list chromatic number) of a simple \(H\)-minor free graph \(G\) where \(H\in \{K_5,K_{3,3}\}\) is at most 5 (resp. at most 8) and we conclude that \(G\) is star 20-colorable. These results generalize the same known results on planar graphs. Moreover, some upper bounds for the coloring numbers of \(H\)-minor free graphs for \(H\in \{K_5,K_{3,3},K_{r,s}\}\) and \(r \leq 2\) are obtained. These results generalize some known results and give some new results on group choice number, group chromatic number, and the choice number of the mentioned graphs with much shorter proofs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M.O., Chappell, G.G., Kierstead, H.A., Kündgen, A., Ramamurthi, R.: Coloring with no 2-colored P4’s. Electron. J. Combin. 11(1), 13 (2004) · Zbl 1053.05045
[2] Borodin, O.V.: On acyclic colorings of planar graphs. Discrete Math. 25(3), 211-236 (1979) · Zbl 0406.05031
[3] Chuang, H., Lai, H.-J., Omidi, G.R., Zakeri, N.: On group choosability of graphs I. Ars Combin. 126, 195-209 (2016) · Zbl 1413.05106
[4] Chuang, H., Lai, H.-J., Omidi, G.R., Wang, K., Zakeri, N.: On group choosability of graphs II. Graphs Combin. 30(3), 549-563 (2014) · Zbl 1294.05059
[5] Diestel, R.: Graph Theory. 3rd edition. Springer, Berlin (2005) · Zbl 1074.05001
[6] Erdös, P., Hajnal, A.: On the chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. 17(1-2), 61-99 (1966) · Zbl 0151.33701
[7] Fertin, G., Raspaud, A., Reed, B.: On star coloring of graphs. In: WG 2001 27th International Workshop on Graph-Theoretic Concepts in Computer Science, Springer Lecture Notes in Computer Science 2204, pp 140-153 (2001) · Zbl 1042.68628
[8] Grünbaum, B.: Acyclic colorings of planar graphs. Israel J. Math. 14, 390-408 (1973) · Zbl 0265.05103
[9] Havet, F., Kang, R., Müller, T., Sereni, J.-S.: Circular choosability. J. Graph Theory 61(4), 241-270 (2009) · Zbl 1180.05044
[10] Jaeger, F., Linial, N., Payan, C., Tarsi, M.: Group connectivity of graphs—a nonhomogeneous analogue of nowhere-zero flow properties. J. Combin. Theory Ser. B 56(2), 165-182 (1992) · Zbl 0824.05043
[11] Mohar, B.: Choosability for the Circular Chromatic Number. Problem of the month. http://www.fmf.uni-lj.si/mohar/ (2002)
[12] Norine, S., Wong, T.-L., Zhu, X.: Circular choosability via combinatorial Nullstellensatz. J. Graph Theory 59(3), 190-204 (2008) · Zbl 1191.05040
[13] Omidi, G.R.: A note on group choosability of graphs with girth at least 4. Graphs Combin. 27(2), 269-273 (2011) · Zbl 1234.05100
[14] Zhu, X.: Circular choosability of graphs. J. Graph Theory 48(3), 210-218 (2005) · Zbl 1065.05044
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.