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
© 2023 | Università degli studi di Verona
CSS e script comuni siti DOL - frase 9957