×

Tutte’s edge-colouring conjecture. (English) Zbl 0883.05055

In 1966 Tutte conjectured that every 2-connected cubic graph not containing the Petersen graph as a minor is 3-edge-colourable. The conjecture is still open, but it is shown in this paper that it is true in general, provided that it is true for two special kinds of cubic graphs that are almost planar.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cameron, P. J.; Chetwynd, A. G.; Watkins, J. J., Decomposition of snarks, J. Graph Theory, 11, 13-19 (1987) · Zbl 0612.05030
[2] Goldberg, M. K., Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory Ser. B, 31, 282-291 (1981) · Zbl 0449.05037
[3] Isaacs, R., Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82, 221-239 (1975) · Zbl 0311.05109
[4] Preissmann, M., \(C\), Ann. Discrete Math., 17, 559-565 (1983) · Zbl 0523.05060
[5] N. Robertson, P. D. Seymour, R. Thomas, 1995, Excluded minors in cubic graphs; N. Robertson, P. D. Seymour, R. Thomas, 1995, Excluded minors in cubic graphs
[6] Seymour, P. D., Disjoint paths in graphs, Discrete Math., 29, 293-309 (1980) · Zbl 0457.05043
[7] P. D. Seymour, K. Truemper, A Petersen on a pentagon; P. D. Seymour, K. Truemper, A Petersen on a pentagon
[8] Tait, P. G., Note on a theorem in geometry of position, Trans. Roy. Soc. Edinburgh, 29, 657-660 (1880) · JFM 12.0409.01
[9] Tutte, W. T., On the algebraic theory of graph colorings, J. Combin. Theory, 1, 15-50 (1966) · Zbl 0139.41402
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.