# zbMATH — the first resource for mathematics

Choosability, edge choosability and total choosability of outerplane graphs. (English) Zbl 0972.05021
If each vertex $$v$$ of a graph $$G$$ is assigned a list $$L(v)$$ of possible colors and $$G$$ has a proper coloring $$\sigma$$ such that $$\sigma(v)\in L(v)$$ for all $$v$$, then we say that $$G$$ is $$L$$-colorable. If $$|L(v)|= k$$ for all $$v$$ and if $$G$$ is $$L$$-colorable for each such $$L$$, then $$G$$ is said to be $$k$$-choosable. By considering colorings for $$E(G)$$ and for $$E(G)\cup V(G)$$ we can define parallel notions such as edge choosability and total choosability. Several relations for these quantities and, in particular, the list edge coloring conjecture for outerplane graphs are proved.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049  Appel, K.; Haken, W., Every planar map is four colorable, (1989), American Mathematical Society Providence, RI · Zbl 0681.05027  Bollobás, B.; Harris, A.J., List-coloring of graphs, Graphs comb., 1, 115-127, (1985) · Zbl 0606.05027  Bollobás, B.; Hind, H.R., A new upper bound for the List chromatic number, Discrete math., 74, 65-75, (1989) · Zbl 0674.05027  Borodin, O.V.; Woodall, D.R., Thirteen colouring numbers for outerplane graphs, Bul. inst. combin. and appl., 14, 87-100, (1995) · Zbl 0836.05026  Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., List edge and List total coloring of multigraphs, J. comb. theory B, 71, 184-204, (1997) · Zbl 0876.05032  Ellingham, M.N.; Goddyn, L., List edge colorings of some 1-factorable multigraphs, Combinatorica, 16, 343-352, (1996) · Zbl 0860.05035  Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)  Fleischner, H.; Stiebitz, M., A solution to a coloring problem of P. erdős, Discrete math., 101, 39-48, (1992)  Galvin, F., The List chromatic index of a bipartite multigraph, J. comb. theory B, 63, 153-158, (1995) · Zbl 0826.05026  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  Häggkvist, R.; Janssen, J., New bounds on the List-chromatic index of the complete graph and other simple graphs, Combin. probab. comput., 6, 295-313, (1997) · Zbl 0880.05035  Kahn, J., Asymptotics of the List-chromatic index for multigraphs, Random struct. algor., 17, 117-156, (2000) · Zbl 0956.05038  Peterson, D.; Woodall, D.R., Edge-choosability in line-perfect multigraphs, Discrete math., 202, 191-199, (1999) · Zbl 0928.05017  Thomassen, C., Every planar graph is 5-choosable, J. comb. theory B, 62, 180-181, (1994) · Zbl 0805.05023  Thomassen, C., 3-List coloring planar graphs of girth 5, J. comb. theory B, 64, 101-107, (1995) · Zbl 0822.05029  Vizing, V.G., Vertex colorings with given colors (in Russian), Metody diskret. analiz., 29, 3-10, (1976) · Zbl 1249.90303  Voigt, M., List colorings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030  Woodall, D.R., Edge-choosability of multicircuits, Discrete math., 202, 271-277, (1999) · Zbl 0928.05018  Zhongfu, Zhang; Jianxun, Zhang; Jianfang, Wang, The total chromatic number of some graphs, Sci. sin. A, 31, 1434-1441, (1988) · Zbl 0664.05017
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.