Seminar of Graph Theory - Róbert Lukoťka (21.2.2019)

Thursday 21.2.2019 at 9:50, Lecture room M/213

---

Róbert Lukoťka:
Three results on cubic graphs

Abstract:
The oddness of a bridgeless cubic graph $G$ is the minimal number of odd circuits in a $2$-factor of $G$. The weak oddness of $G$ is the minimal number of odd components in an even factor of $G$. The resistance of $G$ is the minimal number of vertices that have to be deleted in order to get a $3$-edge-colourable graph from $G$.

As the first result we show that there exist graphs with weak oddness $4$, resistance $4$, and arbitrarily large oddness [I. Allie: Oddness to resistance ratios in cubic graphs, Discrete Mathematics 342 (2019), 387--392].

Second, we show how to decide $3$-edge-colourability, determine the oddness, the weak oddness, and the resistance of a $n$ vertex cubic graph $G$ in time ${\cal O}^*(3^{(1/6+\varepsilon)\cdot n})$. [Joint work with a group of people from KAMAK problem solving seminar].

Third, we show that that if a cubic graph has nowhere-zero $A$-flow (where $A$ is an abelian group) or $k$-flow then it has also a nowhere-zero $A$-flow or $k$-flow where the edges incident with one vertex have their flow values and orientations prescribed (subject to obvious necessary conditions) [M.~DeVos: Flows on Bidirected Graphs, arXiv:1310.8406; Y.~Lu, R.~Luo, C.-Q.~Zhang: Multiple weak $2$-linkage and its applications on integer flows of signed graphs, European Journal of Combinatorics 69 (2018), 36--48].

---