✦ LIBER ✦

Tutte's Edge-Colouring Conjecture

✍ Scribed by Neil Robertson; Paul Seymour; Robin Thomas

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 340 KB
Volume: 70
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1752

No coin nor oath required. For personal study only.

✦ Synopsis

dedicated to professor w. t. tutte on the occasion of his eightieth birthday

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.

1997 Academic Press

1. Introduction

The following well-known conjecture is due to Tutte [9]:

(1.1) Conjecture. Every 2-connected cubic graph with no Petersen minor is 3-edge-colourable.

📜 SIMILAR VOLUMES

Fractional Colouring and Hadwiger's Conj

Fractional Colouring and Hadwiger's Conjecture

✍ Bruce Reed; Paul Seymour 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 162 KB

On characterizing Vizing's edge colourin

On characterizing Vizing's edge colouring bound

✍ Penny Haxell; Jessica McDonald 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

**Features recent advances and new applications in graph edge coloring**Reviewing recent advances in the Edge Coloring Problem, __Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture__ provides an overview of the current state of the science, explaining the interconnections among the resu

Tutte's 5-flow conjecture for the projec

Tutte's 5-flow conjecture for the projective plane

✍ Richard Steinberg 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB

Heawood proved that every planar graph with no 1-cycles is vertex 5colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjectu

Tutte′s 3-Flow Conjecture and Short Cycl

Tutte′s 3-Flow Conjecture and Short Cycle Covers

✍ G.H. Fan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 285 KB

In this paper we prove: (i) If a graph \(G\) has a nowhere-zero 6 -llow \(\phi\) such that \(\left|E_{\text {odd }}(\phi)\right| \geqslant \frac{2}{3}|E(G)|\), then \(G\) has a cycle cover in which the sum of the lengths of the cycles in the cycle cover is at most \(\frac{44}{27}|E(G)|\), where \(E_

Tutte's 5-flow conjecture for graphs of

Tutte's 5-flow conjecture for graphs of nonorientable genus 5

✍ Steffen, Eckhard 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 577 KB

We develop four constructions for nowhere-zero 5-flows of 3-regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counterexample to Tutte's 5-Flow Conjecture is of order 244 and therefore every bridgeless graph of nonorientable genus 5 5 has a nowhere

The Edge-Orbit Conjecture of Babai

✍ A.J. Goodman 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 414 KB

This paper proves the Edge-Orbit Conjecture stated by L. Babai (1981, in "Combinatorics" (H. N. V. Temperley, Ed.), pp. 1-40, Cambridge Univ. Press, London). We say a graph \(X\) represents a group \(G\) if \(\operatorname{Aut}(X) \cong G\). Let \(m_{c}(G)\) be the minimum number of edge orbits amon