Flows and bisections in cubic graphs

Giuseppe Mazzuoccolo - Università di Verona
Date and time
Tuesday, November 8, 2016 at 3:00 PM - Rinfresco 14.45, inizio seminario 15.00.
Ca' Vignal - Piramide, Floor 0, Hall Verde
Programme Director
Romeo Rizzi
External reference
Publication date
September 19, 2016
Computer Science  


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. 

© 2002 - 2021  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234