7 papers
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…
Sandwiching biregular random graphs
Tereza Klimošová, Christian Reiher, Andrzej Ruciński +1
Let be a uniformly random -edge subgraph of the complete bipartite graph with bipartition , where . Given a real number $p \in [0,1…
Covering minimal separators and potential maximal cliques in -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk +1
A graph is called -free} if it does not contain a -vertex path as an induced subgraph. While -free graphs are exactly cographs, the structure of -free graphs for…
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
Thomas Bellitto, Tereza Klimošová, Martin Merker +2
We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red…
Edge-partitioning 3-edge-connected graphs into paths
Tereza Klimošová, Stéphan Thomassé
We show that for every l, there exists d_l such that every 3-edge-connected graph with minimum degree d_l can be edge-partitioned into paths of length l (provided that its number o…
Edge-decomposing graphs into coprime forests
Tereza Klimošová, Stéphan Thomassé
The Barat-Thomassen conjecture, recently proved in [Bensmail et al.: A proof of the Barat-Thomassen conjecture. J. Combin. Theory Ser. B, 124:39-55, 2017.], asserts that for every…