Seminár z teórie grafov - Robert Lukoťka (30.3.2017)

vo štvrtok 30.3.2017 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: RNDr. Robert Lukoťka, PhD.

Názov: 6-circuits in 2-factors of cubic graphs

Termín: 30.3.2017, 9:50 hod., M/213

Abstract:
We prove that a bridgeless cubic graph $G$ of girth $6$ on $n$ vertices has a $2$-factor $F$ such that at most $9/13 \cdot n$ vertices of $G$ are in circuits of length $6$ of $F$. Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every simple $2$-connected cubic graph on $n$ vertices contains a spanning closed walk of length at most $9/7 \cdot n-1$. We use the technique from our proof to provide an alternative and shorter proof of this statement. Our analysis of $6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the lack of analysis of the $7$-circuits. We provide a very basic analysis of $7$-circuits to show that there exists $\epsilon>0$ such that every simple $2$-connected cubic graph on $n$ vertices contains a spanning closed walk of length at most $(9/7 - \epsilon) \cdot n-1$.

---