×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
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
[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
[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. 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.