z-logo
Premium
3‐Flows and Combs
Author(s) -
Silva Cândida Nunes,
Lucchesi Cláudio L.
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21785
Subject(s) - mathematics , combinatorics , conjecture , counterexample , graph , connectivity , enhanced data rates for gsm evolution , flow (mathematics) , discrete mathematics , geometry , computer science , telecommunications
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here