A k-weak bisection of a cubic graph G is a partition of the vertex-set of G into two parts V 1 and V 2 of equal size, such that each connected component of the subgraph of G induced by V i (i = 1, 2) is a tree of at most k − 2 vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere-zero r-flow has a [r]-weak bisection. In this article, we study problems related to the existence of k-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.

Flows and Bisections in Cubic Graphs / Esperet, L.; Mazzuoccolo, Giuseppe; Tarsi, M.. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 86:2(2017), pp. 149-158. [10.1002/jgt.22118]

### Flows and Bisections in Cubic Graphs

#### Abstract

A k-weak bisection of a cubic graph G is a partition of the vertex-set of G into two parts V 1 and V 2 of equal size, such that each connected component of the subgraph of G induced by V i (i = 1, 2) is a tree of at most k − 2 vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere-zero r-flow has a [r]-weak bisection. In this article, we study problems related to the existence of k-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
86
2
149
158
Flows and Bisections in Cubic Graphs / Esperet, L.; Mazzuoccolo, Giuseppe; Tarsi, M.. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 86:2(2017), pp. 149-158. [10.1002/jgt.22118]
Esperet, L.; Mazzuoccolo, Giuseppe; Tarsi, M.
File in questo prodotto:
File
revision4.pdf

Accesso riservato

Dimensione 309.68 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1310836`