Tutte's edge-colouring conjecture

Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1006/jctb.1997.1752

Tutte's edge-colouring conjecture

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journal › Article › peer-review

41 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	166-183
Number of pages	18
Journal	Journal of Combinatorial Theory. Series B
Volume	70
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1997.1752
State	Published - May 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1997.1752

Cite this

@article{a833fd3f448346ac945b8543cfc46c5b,

title = "Tutte's edge-colouring conjecture",

abstract = "Tutte made the conjecture in 1966 that every 2-connected cubic graph not containing the Petersen graph as a minor is 3-edge-colourable. The conjecture is still open, but we show that it is true, in general, provided it is true for two special kinds of cubic graphs that are almost planar.",

author = "Neil Robertson and Paul Seymour and Robin Thomas",

note = "Funding Information: * Research partially supported by DIMACS, by ONR Grant N00014-92-J-1965, and by NSF Grant DMS-8903132, and partially performed under a consulting agreement with Bellcore. Funding Information: -Research partially supported by DIMACS, by ONR Grant N00014-93-1-0325, and by NSF Grant DMS-9303761, and partially performed under a consulting agreement with Bellcore.",

year = "1997",

month = may,

doi = "10.1006/jctb.1997.1752",

language = "English (US)",

volume = "70",

pages = "166--183",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Tutte's edge-colouring conjecture

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

N1 - Funding Information: * Research partially supported by DIMACS, by ONR Grant N00014-92-J-1965, and by NSF Grant DMS-8903132, and partially performed under a consulting agreement with Bellcore. Funding Information: -Research partially supported by DIMACS, by ONR Grant N00014-93-1-0325, and by NSF Grant DMS-9303761, and partially performed under a consulting agreement with Bellcore.

PY - 1997/5

Y1 - 1997/5

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

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

UR - https://www.scopus.com/pages/publications/0031145823

UR - https://www.scopus.com/inward/citedby.url?scp=0031145823&partnerID=8YFLogxK

U2 - 10.1006/jctb.1997.1752

DO - 10.1006/jctb.1997.1752

M3 - Article

AN - SCOPUS:0031145823

SN - 0095-8956

VL - 70

SP - 166

EP - 183

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Tutte's edge-colouring conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this