# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
unique list coloring
Full Text:
##### References:
  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  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049  Bollobás, B.; Sauer, N., Uniquely colorable graphs with large girth, Canad. J. math., 28, 1340-1344, (1976) · Zbl 0344.05115  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  Chao, C.; Chen, Z., On uniquely 3-colorable graphs, Discrete math., 112, 21-27, (1993) · Zbl 0780.05021  Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)  Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026  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  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  Harary, F.; Hedetniemi, S.T.; Robinson, R.W., Uniquely colorable graphs, J. combin. theory, 6, 264-270, (1969) · Zbl 0175.50205  Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046  Vizing, V.G., Vertex colorings with given colors, Metody diskret. anal., 29, 3-10, (1976), (in Russian) · Zbl 1249.90303  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.