zbMATH — the first resource for mathematics

A refinement of choosability of graphs. (English) Zbl 1430.05046
Summary: Assume \(k\) is a positive integer, \(\lambda = \{k_1, k_2, \ldots, k_q\}\) is a partition of \(k\) and \(G\) is a graph. A \(\lambda\)-assignment of \(G\) is a \(k\)-assignment \(L\) of \(G\) such that the colour set \(\bigcup_{v \in V(G)} L(v)\) can be partitioned into \(q\) subsets \(C_1 \cup C_2 \ldots \cup C_q\) and for each vertex \(v\) of \(G,\ |L(v) \cap C_i| = k_i\). We say \(G\) is \(\lambda\)-choosable if for each \(\lambda\)-assignment \(L\) of \(G, G\) is \(L\)-colourable. It follows from the definition that if \(\lambda = \{k\}\), then \(\lambda\)-choosable is the same as \(k\)-choosable, if \(\lambda = \{1, 1, \ldots, 1\}\), then \(\lambda\)-choosable is equivalent to \(k\)-colourable. For the other partitions of \(k\) sandwiched between \(\{k\}\) and \(\{1, 1, \ldots, 1 \}\) in terms of refinements, \( \lambda \)-choosability reveals a complex hierarchy of colourability of graphs. We prove that for two partitions \(\lambda, \lambda^\prime\) of \(k\), every \(\lambda \)-choosable graph is \(\lambda^\prime \)-choosable if and only if \(\lambda^\prime\) is a refinement of \(\lambda \). Then we study \(\lambda \)-choosability of special families of graphs. The four colour theorem says that every planar graph is \(\{1, 1, 1, 1 \}\)-choosable.
A very recent result of A. Kemnitz and M. Voigt [Electron. J. Comb. 25, No. 2, Research Paper P2.46, 5 p. (2018; Zbl 1388.05048)] implies that for any partition \(\lambda\) of 4 other than \(\{1, 1, 1, 1 \}\), there is a planar graph which is not \(\lambda \)-choosable. We observe that, in contrast to the fact that there are non-4-choosable 3-chromatic planar graphs, every 3-chromatic planar graph is \(\{1, 3 \}\)-choosable, and that if \(G\) is a planar graph whose dual \(G^\ast\) has a connected spanning Eulerian subgraph, then \(G\) is \(\{2, 2 \}\)-choosable. We prove that if \(n\) is a positive even integer, \( \lambda\) is a partition of \(n - 1\) in which each part is at most 3, then \(K_n\) is edge \(\lambda \)-choosable. Finally we study relations between \(\lambda \)-choosability of graphs and colouring of signed graphs and generalized signed graphs. A conjecture of E. Máčajová et al. [Electron. J. Comb. 23, No. 1, Research Paper P1.14, 10 p. (2016; Zbl 1329.05116)] that every planar graph is signed 4-colcourable is recently disproved by F. Kardoš and J. Narboni [“On the 4-color theorem for signed graphs ”, Preprint, arXiv:1906.05638]. We prove that every signed 4-colourable graph is weakly 4-choosable, and every signed \(Z_4\)-colourable graph is \(\{1, 1, 2 \}\)-choosable. The later result combined with the above result of Kemnitz and Voigt disproves a conjecture of Y. Kang and E. Steffen [J. Graph Theory 87, No. 2, 135–148 (2018; Zbl 1383.05103)] that every planar graph is signed \(Z_4\)-colourable. We shall show that a graph constructed by G. Wegner [Isr. J. Math. 14, 409–412 (1973; Zbl 0265.05104)] is also a counterexample to Kang and Steffen’s conjecture, and present a new construction of a non-\(\{1, 3 \}\)-choosable planar graphs.

05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05A17 Combinatorial aspects of partitions of integers
Full Text: DOI arXiv
[1] Bernshteyn, A.; Kostochka, A., On differences between DP-coloring and list coloring, Mat. Tr., 21, 2, 61-71 (2018), (Russian)
[2] Bernshteyn, A.; Kostochka, A.; Zhu, X., DP-colorings of graphs with high chromatic number, European J. Combin., 65, 122-129 (2017) · Zbl 1369.05065
[3] Borodin, O. V.; Glebov, A. N.; Raspaud, A., Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable, Discrete Math., 310, 2584-2594 (2010) · Zbl 1203.05048
[4] Borodin, O. V.; Glebov, A. N.; Raspaud, A.; Salavatipour, M. R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B, 93, 303-331 (2005) · Zbl 1056.05052
[5] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B, 71, 184-204 (1997) · Zbl 0876.05032
[6] Choi, H.; Kwon, Y., On t-common list-colorings, Electron. J. Combin., 24, 3 (2017), Paper 3.32, 10 pp · Zbl 1369.05069
[7] Cohen-Addad, V.; Hebdige, M.; Král, D.; Li, Z.; Salgado, E., Steinberg’s conjecture is false, J. Combin. Theory Ser. B, 122, 452-456 (2017) · Zbl 1350.05018
[8] Dvořák, Z.; Postle, L., List-coloring embedded graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B, 129, 38-54 (2018) · Zbl 1379.05034
[9] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing (1979), Congressus Numerantium XXVI), 125-157
[10] Jaeger, F.; Linial, N.; Payan, C.; Tarsi, M., Group connectivity of graphs—a non-homongenous analogue of nowhere-zero flow, J. Combin. Theory Ser. B, 56, 165-182 (1992) · Zbl 0824.05043
[11] Jiang, Y.; Liu, D.; Yeh, Y.; Zhu, X., Colouring of generalized signed triangle free planar graphs, Discrete Math., 342, 3, 836-843 (2019) · Zbl 1403.05049
[12] Y. Jiang, X. Zhu, 4-colouring of generalized signed planar graphs, 2019, manuscript.
[13] L. Jin, T. Wong, X. Zhu, Colouring of generalized signed graphs, 2018, submitted for publication.
[14] Kang, Y.; Steffen, E., The chromatic spectrum of signed graphs, Discrete Math., 339, 2660-2663 (2016) · Zbl 1339.05169
[15] Kang, Y.; Steffen, E., Circular coloring of signed graphs, J. Graph Theory, 00, 1-4 (2017)
[16] Y. Kang, E. Steffen, personal communication, 2017.
[17] Kardoš, F.; Narboni, J., On the 4-color theorem for signed graphs
[18] Kemnitz, A.; Voigt, M., A note on non-4-list colorable planar graphs, Electron. J. Combin., 25, 2, Article #P2.46 pp. (2018) · Zbl 1388.05048
[19] R. Kim, S. Kim, X. Zhu, Signed colouring and list colouring of k-chromatic graphs, 2018, manuscript.
[20] Kündgen, A.; Ramamurthi, R., Coloring face-hypergraphs of graphs on surfaces, J. Combin. Theory Ser. B, 85, 307-337 (2002) · Zbl 1029.05057
[21] Máčajová, E.; Raspaud, A.; Škoviera, M., The chromatic number of a signed graph, Electron. J. Combin., 23, 1 (2016), #P1.14 · Zbl 1329.05116
[22] Mirzakhani, M., A small non-4-choosable planar graph, Bull. Inst. Combin. Appl., 17, 15-18 (1996) · Zbl 0860.05029
[23] Montassier, M., A note on the not 3-choosability of some families of planar graphs, Inform. Process. Lett., 99, 68-71 (2006) · Zbl 1184.05048
[24] Thomassen, C., Every planar graph is 5-choosable, J. Combin. Theory Ser. B, 62, 1, 180-181 (1994) · Zbl 0805.05023
[25] Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i Shem, 3-10 (1976), p. 101, (in Russian)
[26] Voigt, M., List colourings af planar graphs, Discrete Math., 120, 215-910 (1993) · Zbl 0790.05030
[27] Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete Math., 146, 1-3, 325-328 (1995) · Zbl 0843.05034
[28] Wegner, G., Note on a paper of B. Grünbaum on acyclic colorings, Israel J. Math., 14, 409-412 (1973) · Zbl 0265.05104
[29] West, D., Introduction to Graph Theory (1996), Prentice Hall, Inc.: Prentice Hall, Inc. Upper Saddle River, NJ · Zbl 0845.05001
[30] Zaslavsky, T., Signed graph coloring, Discrete Math., 39, 215-228 (1982) · Zbl 0487.05027
[31] Zhu, X., Multiple list colouring of planar graphs, J. Combin. Theory Ser. B, 122, 794-799 (2017) · Zbl 1350.05046
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.