×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[2] Appel, K.; Haken, W., Every planar map is four colorable, (1989), American Mathematical Society Providence, RI · Zbl 0681.05027
[3] Bollobás, B.; Harris, A.J., List-coloring of graphs, Graphs comb., 1, 115-127, (1985) · Zbl 0606.05027
[4] Bollobás, B.; Hind, H.R., A new upper bound for the List chromatic number, Discrete math., 74, 65-75, (1989) · Zbl 0674.05027
[5] Borodin, O.V.; Woodall, D.R., Thirteen colouring numbers for outerplane graphs, Bul. inst. combin. and appl., 14, 87-100, (1995) · Zbl 0836.05026
[6] 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
[7] Ellingham, M.N.; Goddyn, L., List edge colorings of some 1-factorable multigraphs, Combinatorica, 16, 343-352, (1996) · Zbl 0860.05035
[8] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[9] Fleischner, H.; Stiebitz, M., A solution to a coloring problem of P. erdős, Discrete math., 101, 39-48, (1992)
[10] Galvin, F., The List chromatic index of a bipartite multigraph, J. comb. theory B, 63, 153-158, (1995) · Zbl 0826.05026
[11] 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
[12] 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
[13] Kahn, J., Asymptotics of the List-chromatic index for multigraphs, Random struct. algor., 17, 117-156, (2000) · Zbl 0956.05038
[14] Peterson, D.; Woodall, D.R., Edge-choosability in line-perfect multigraphs, Discrete math., 202, 191-199, (1999) · Zbl 0928.05017
[15] Thomassen, C., Every planar graph is 5-choosable, J. comb. theory B, 62, 180-181, (1994) · Zbl 0805.05023
[16] Thomassen, C., 3-List coloring planar graphs of girth 5, J. comb. theory B, 64, 101-107, (1995) · Zbl 0822.05029
[17] Vizing, V.G., Vertex colorings with given colors (in Russian), Metody diskret. analiz., 29, 3-10, (1976) · Zbl 1249.90303
[18] Voigt, M., List colorings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[19] Woodall, D.R., Edge-choosability of multicircuits, Discrete math., 202, 271-277, (1999) · Zbl 0928.05018
[20] 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.