zbMATH — the first resource for mathematics

A relation between choosability and uniquely list colorability. (English) Zbl 1100.05032
A list assignment \(L\) of a graph \(G\) is a function that assigns a set of colors to each vertex of \(G\). Graph \(G\) is (uniquely) \(L\)-colorable if there is at least (exactly) one function that assigns to each vertex \(v\) of \(G\) a color from \(L(v)\) such that any two adjacent vertices are assigned distinct colors. The definitions of an edge-list assignment and a uniquely \(L\)-edge-colorable graph are analogous.
The main result of this paper says that if \(G\) is a uniquely \(L\)-colorable graph with \(n\) vertices and \(m\) edges such that the sum of \(| L(v)| \) over all vertices \(v\) of \(G\) equals \(n+m\), then \(G\) is also \(L'\)-colorable for any list assignment \(L'\) satisfying \(| L'(v)| =| L(v)| \) for each vertex \(v\) of \(G\).
The proof is based on an algebraic technique developed by N. Alon and M. Tarsi [Combinatorica 12, No. 2, 125–134 (1992; Zbl 0756.05049)]. As a corollary, it is shown that if a connected non-regular multigraph with an edge-list assignment \(L\) satisfies \(L(\{u,v\})=\max\{d(u),d(v)\}\) for each edge \(\{u,v\}\), then it is not uniquely \(L\)-edge-colorable. The authors conjecture that this result holds also for any regular graph \(G\) of degree at least two and verify it in the case that \(G\) is bipartite.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Akbari, S.; Mirrokni, V.S.; Sadjad, B.S., \(K_r\)-free uniquely colorable graphs with minimum possible edges, J. combin. theory ser. B, 82, 2, 316-318, (2001) · Zbl 1027.05040
[2] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049
[3] Bollobás, B.; Sauer, N., Uniquely colorable graphs with large girth, Canad. J. math., 28, 1340-1344, (1976) · Zbl 0344.05115
[4] 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
[5] Chao, C.; Chen, Z., On uniquely 3-colorable graphs, Discrete math., 112, 21-27, (1993) · Zbl 0780.05021
[6] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[7] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[8] Ganjali, Y.G.; Ghebleh, M.; Hajiabolhassan, H.; Mirzazadeh, M.; Sadjad, B.S., Uniquely 2-List colorable graphs, Discrete appl. math., 119, 3, 217-225, (2002) · Zbl 0999.05037
[9] Häggkvist, R.; Chetwynd, A., Some upper bounds on the total and List chromatic numbers of multigraphs, J. graph theory, 16, 503-516, (1992) · Zbl 0814.05038
[10] Harary, F.; Hedetniemi, S.T.; Robinson, R.W., Uniquely colorable graphs, J. combin. theory, 6, 264-270, (1969) · Zbl 0175.50205
[11] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046
[12] Vizing, V.G., Vertex colorings with given colors, Metody diskret. anal., 29, 3-10, (1976), (in Russian) · Zbl 1249.90303
[13] Xu, S., The size of uniquely colorable graphs, J. combin. theory ser. B, 50, 319-320, (1990) · Zbl 0722.05032
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.