Flows and bisections in cubic graphs

Relatore
Giuseppe Mazzuoccolo - Università di Verona
Data e ora
martedì 8 novembre 2016 alle ore 15.00 - Rinfresco 14.45, inizio seminario 15.00.
Luogo
Ca' Vignal - Piramide, Piano 0, Sala Verde
Referente
Romeo Rizzi
Referente esterno
Data pubblicazione
19 settembre 2016
Dipartimento
Informatica  

Riassunto

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  Universit√† degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234