Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs (Q1356437)

From MaRDI portal
Revision as of 16:41, 6 February 2024 by Daniel (talk | contribs) (‎Created claim: Wikidata QID (P12): Q123027379, #quickstatements; #temporary_batch_1707232231678)
scientific article
Language Label Description Also known as
English
Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs
scientific article

    Statements

    Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs (English)
    0 references
    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
    0 references
    Tait colouring
    0 references
    bottleneck
    0 references
    cubic graph
    0 references

    Identifiers