Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs (Q1356437)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs |
scientific article; zbMATH DE number 1018496
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs |
scientific article; zbMATH DE number 1018496 |
Statements
Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs (English)
0 references
9 June 1997
0 references
A bottleneck in a non-Tait-colourable cubic graph \(G= (V,E)\) is a minimal set \(\mathcal B\) of odd cuts such that, for any \(S\subseteq E\), either \(S\) or \(E\backslash S\) contains at least one member of \(\mathcal B\). F. Holroyd and F. Loupekine conjectured that in any non-Tait-colourable bridgeless cubic graph, the cuts of orders 3 and 5 form a bottleneck. E. Steffen proves that this conjecture is not true for any cyclically 6-edge non-Tait-colourable cubic graph.
0 references
Tait colouring
0 references
bottleneck
0 references
cubic graph
0 references
