The existence of a bisection of the vertex set of a cubic graph G with small monochromatic components is strictly related to the existence of certain flows. In particular, a circular nowhere-zero r-flow in G implies a bisection, where every connected subgraph on r-1 vertices intersects both parts of the bisection. This is related to a recent conjecture of Ban and Linial, stating that any bridgeless cubic graph, other than the Petersen graph, admits a bisection, where the graph induced by each part of the bisection consists of connected components on at most two vertices. Here, we present some recent progress on Ban and Linial conjecture.
Strada le Grazie 15
VAT number 01541040232
Italian Fiscal Code 93009870234
© 2019 | Verona University | Credits