4 papers · 1 filter
Star subdivisions and connected even factors in the square of a graph
Jan Ekstein, Přemysl Holub, Tomáš Kaiser +2
For any positive integer , a -factor in a graph is a connected even factor with maximum degree at most . We prove that if every induced in a gra…
Multiple Petersen subdivisions in permutation graphs
Tomáš Kaiser, Jean-Sébastien Sereni, Zelealem Yilma
A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove…
Hamilton cycles in 5-connected line graphs
Tomáš Kaiser, Petr Vrána
A conjecture of Carsten Thomassen states that every 4-connected line graph is hamiltonian. It is known that the conjecture is true for 7-connected line graphs. We improve this by s…
Covering a graph by forests and a matching
Tomas Kaiser, Mickael Montassier, Andre Raspaud
We prove that for any positive integer , the edges of any graph whose fractional arboricity is at most can be decomposed into forests and a matching.