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

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

---

Prednášajúci: Robert Lukoťka

Názov: Perfect matchings in highly cyclically connected regular graphs

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

Abstrakt:
Let $G$ be a $d$-regular cyclically $(d-1+2k)$-edge-connected graph (with $k\geq 0$) of even order. A leaf matching operation (LMO) on $G$ consists of removing a vertex of degree $1$ together with its neighbour from $G$. We show that for any given set $X$ of $d-1+k$ edges, there is no $1$-factor of $G$ avoiding $X$ if and only if either an isolated vertex can be obtained by a series of LMO operations in $G-X$ or $G-X$ has an independent set that contains more than half of the vertices of $G$. We show how signed graphs are useful to verify the two conditions of the statement by proving several statements on cubic graphs. We prove that for every integer $k$, if $G$ is sufficiently cyclically edge-connected, then for any three distant paths, there exists a $2$-factor of $G$ that contains one of these paths. For paths of length $3$ and $4$ we analyse the cases when only one or two (possibly intersecting) paths are given. As a consequence, we obtain that for cyclically 7-edge-connected cubic graph $G$ and a vertex $v$ of $G$ there exists a $2$-factor such that $v$ is in cycle of length greater than $7$.

This is joint work with Edita Rollová (University of West Bohemia, Pilsen, Czech Republic).

---