Snarks and Flow-Critical Graphs |
| |
| Institution: | 1. DComp – CCTS – UFSCAR – Sorocaba, SP, Brazil;2. Faculty of Computing – FACOM-UFMS – Campo Grande, MS, Brazil;1. Institute of Math. Sciences, IV Cross Road, Taramani, Chennai 600 113, India;2. School of Comp. Science, Simon Fraser University, Burnaby, Canada V5A 1S6;3. DIMAP and Math. Institute, University of Warwick, Coventry CV4 7AL, UK |
| |
| 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. |
| |
| Keywords: | Tutteʼs Flow Conjectures 3-edge-colouring flow-critical graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
