×

zbMATH — the first resource for mathematics

List edge colourings of some 1-factorable multigraphs. (English) Zbl 0860.05035
The list edge colouring conjecture asserts that, given any multigraph \(G\) with chromatic index \(k\), and any set system \(\{S_e:e\in E(G)\}\) with each \(|S_e|=k\), we can choose elements \(s_e\in S_e\) such that \(s_e\neq s_f\) whenever \(e\) and \(f\) are adjacent edges. Using a technique of Alon and Tarsi which involves the graph monomial \(\prod\{x_u-x_v: uv\in E\}\) of an oriented graph, this conjecture is verified for certain families of 1-factorable multigraphs, including 1-factorable planar graphs.

MSC:
05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon: Restricted colorings of graphs, in:?Surveys in Combinatorics?, Proc. 14th British Combinatorial Conference, London Mathematical Society Lecture Notes Series 187, edited by K. Walker, Cambridge University Press, 1993, 1-33. · Zbl 0791.05034
[2] N. Alon, andM. Tarsi: Colorings and orientations of graphs,Combinatorica,12, (1992), 125-134. · Zbl 0756.05049 · doi:10.1007/BF01204715
[3] B. Bollob?s, andH. R. Hind: A new upper bound for the list chromatic number,Discrete Math.,74, (1989), 65-75. · Zbl 0674.05027 · doi:10.1016/0012-365X(89)90199-4
[4] Amanda Chetwynd, andRoland H?ggkvist: A note on list-colorings,J. Graph Theory,13 (1989), 87-95. · Zbl 0674.05026 · doi:10.1002/jgt.3190130112
[5] P. Erd?s, A. Rubin, andH. Taylor: Choosability in graphs,Congr. Numer.,26, (1979), 125-157.
[6] H. Fleischner, andM. Stiebitz: A solution to a colouring problem of P. Erd?s,Discrete Math,101, (1992), 39-48. · Zbl 0759.05037 · doi:10.1016/0012-365X(92)90588-7
[7] F. Galvin: The list chromatic index of a bipartite multigraph,J. Combin. Theory, Ser. B,63 (1995), 153-159. · Zbl 0826.05026 · doi:10.1006/jctb.1995.1011
[8] R. H?ggkvist, andJ. Janssen: New bounds on the list-chromatic index of the complete graph,Combin. Probab. Comput, to appear.
[9] F. Jaeger: On the Penrose number of cubic diagrams,Discrete Math.,74 (1989), 85-97. · Zbl 0679.05029 · doi:10.1016/0012-365X(89)90201-X
[10] S.-Y. R. Li, andW.-C. W. Li: Independence numbers of graphs and generators of ideals,Combinatorica,1 (1981), 55-61. · Zbl 0524.05037 · doi:10.1007/BF02579177
[11] Julius Petersen: Die Theorie der regul?ren graphs,Acta Math.,15 (1891), 193-220. · JFM 23.0115.03 · doi:10.1007/BF02392606
[12] G. Sabidussi: Binary invariants and orientations of graphs,Discrete Math.,101 (1992), 251-277. · Zbl 0771.05098 · doi:10.1016/0012-365X(92)90607-H
[13] David E. Scheim: The number of edge 3-colorings of a planar cubic graph as a permanent,Discrete Math.,8 (1974), 377-382. · Zbl 0281.05103 · doi:10.1016/0012-365X(74)90157-5
[14] P. D. Seymour: Some unsolved problems on one-factorizations of graphs,Graph Theory and Related Topics, edited by J. A. Bondy and U. S. R. Murty, Academic Press (1979) 367-368.
[15] Andrew Thomason: Cubic graphs with three hamiltonian cycles are not always uniquely edge colourable,J. Graph Theory,6 (1982), 219-221. · Zbl 0495.05025 · doi:10.1002/jgt.3190060218
[16] L. Vigneron: Remarques sur les r?seaux cubiques de classe 3 associ?s au probl?me des quatre couleurs,C. R. Acad. Sc. Paris,223 (1946), 770-772. · Zbl 0060.41605
[17] Roger Penrose: Applications of negative dimensional tensors, in:Combinatorial Mathematics and its Applications, Proc. Conf., Oxford, 1969. Academic Press, London, 1971, 221-244.
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.