On Tutte's extension of the four-colour problem

P. D. Seymour

doi:10.1016/S0095-8956(81)80013-5

On Tutte's extension of the four-colour problem

P. D. Seymour

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

35 Scopus citations

Abstract

In 1966, Tutte presented a problem about matroids which contained as special cases the four-colour problem and two graph-theoretic extensions of it and he gave a conjecture as to the general solution. In this paper we reduce the matroid problem to one of the graph-theoretic special cases (the so-called 4-flow problem), and we show that his general conjecture is correct if it is true in this special case.

Original language	English (US)
Pages (from-to)	82-94
Number of pages	13
Journal	Journal of Combinatorial Theory, Series B
Volume	31
Issue number	1
DOIs	https://doi.org/10.1016/S0095-8956(81)80013-5
State	Published - Aug 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/S0095-8956(81)80013-5

Cite this

@article{af750f031cce46eab86ce74c0192561e,

title = "On Tutte's extension of the four-colour problem",

abstract = "In 1966, Tutte presented a problem about matroids which contained as special cases the four-colour problem and two graph-theoretic extensions of it and he gave a conjecture as to the general solution. In this paper we reduce the matroid problem to one of the graph-theoretic special cases (the so-called 4-flow problem), and we show that his general conjecture is correct if it is true in this special case.",

author = "Seymour, {P. D.}",

year = "1981",

month = aug,

doi = "10.1016/S0095-8956(81)80013-5",

language = "English (US)",

volume = "31",

pages = "82--94",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On Tutte's extension of the four-colour problem

AU - Seymour, P. D.

PY - 1981/8

Y1 - 1981/8

N2 - In 1966, Tutte presented a problem about matroids which contained as special cases the four-colour problem and two graph-theoretic extensions of it and he gave a conjecture as to the general solution. In this paper we reduce the matroid problem to one of the graph-theoretic special cases (the so-called 4-flow problem), and we show that his general conjecture is correct if it is true in this special case.

AB - In 1966, Tutte presented a problem about matroids which contained as special cases the four-colour problem and two graph-theoretic extensions of it and he gave a conjecture as to the general solution. In this paper we reduce the matroid problem to one of the graph-theoretic special cases (the so-called 4-flow problem), and we show that his general conjecture is correct if it is true in this special case.

UR - http://www.scopus.com/inward/record.url?scp=33644561816&partnerID=8YFLogxK

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

U2 - 10.1016/S0095-8956(81)80013-5

DO - 10.1016/S0095-8956(81)80013-5

M3 - Article

AN - SCOPUS:33644561816

SN - 0095-8956

VL - 31

SP - 82

EP - 94

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

On Tutte's extension of the four-colour problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this