Flows and bisections in cubic graphs

Relatore:  Giuseppe Mazzuoccolo - Università di Verona
  martedì 8 novembre 2016 alle ore 15.00 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. 

Ca' Vignal - Piramide, Piano 0, Sala Verde

Romeo Rizzi

Data pubblicazione
19 settembre 2016

Offerta formativa