3‐Flows and Combs |
| |
| Authors: | Cândida Nunes da Silva Cláudio L. Lucchesi |
| |
| Affiliation: | 1. CCTS, FEDERAL UNIVERSITY OF S?O CARLOS – UFSCar, SOROCABA, SP, BRAZIL;2. FACULTY OF COMPUTING, FACOM‐UFMS, CAMPO GRANDE, MS, BRAZIL |
| |
| Abstract: | Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected. |
| |
| Keywords: | 3‐flows nowhere‐zero flows |
|
|
