On Tutte's extension of the four-colour problem

Research output: Contribution to journalArticlepeer-review

22 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 languageEnglish (US)
Pages (from-to)82-94
Number of pages13
JournalJournal of Combinatorial Theory, Series B
Volume31
Issue number1
DOIs
StatePublished - Aug 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On Tutte's extension of the four-colour problem'. Together they form a unique fingerprint.

Cite this