Flows and bisections in cubic graphs

Speaker:  Giuseppe Mazzuoccolo - Università di Verona
  Tuesday, November 8, 2016 at 3:00 PM Rinfresco 14.45, inizio seminario 15.00.
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. 

Place
Ca' Vignal - Piramide, Floor 0, Hall Verde

Programme Director
Romeo Rizzi

External reference
Publication date
September 19, 2016

Studying

Share