Affordable Access

Publisher Website

Snarks and Flow-Critical Graphs

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
44
Identifiers
DOI: 10.1016/j.endm.2013.10.047
Keywords
  • Nowhere-Zerok-Flows
  • TutteʼS Flow Conjectures
  • 3-Edge-Colouring
  • Flow-Critical Graphs

Abstract

Abstract It is well-known that a 2-edge-connected cubic graph has a 3-edge-colouring if and only if it has a 4-flow. Snarks are usually regarded to be, in some sense, the minimal cubic graphs without a 3-edge-colouring. We defined the notion of 4-flow-critical graphs as an alternative concept towards minimal graphs. It turns out that every snark has a 4-flow-critical snark as a minor. We verify, surprisingly, that less than 5% of the snarks with up to 28 vertices are 4-flow-critical. On the other hand, there are infinitely many 4-flow-critical snarks, as every flower-snark is 4-flow-critical. These observations give some insight into a new research approach regarding Tutteʼs Flow Conjectures.

There are no comments yet on this publication. Be the first to share your thoughts.