14 citations · 26 across the 13 of their papers we have counts for
16 papers
3-Coloring or -free Diameter Two Graphs
Tereza Klimošová, Vibha Sahlot
The question of whether 3-Coloring can be solved in polynomial-time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the p…
Antipaths in oriented graphs
Tereza Klimošová, Maya Stein
We show that for any natural number , any oriented graph of minimum semidegree at least contains an antidirected path of length . In fact, a slightly we…
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…
Colouring -Free Graphs
Tereza Klimošová, Josef Malík, Tomáš Masařík +3
The -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for a fixed integer such that no two adjacent vertices are coloured a…
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…
Polynomial-time algorithm for Maximum Weight Independent Set on -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk +1
In the classic Maximum Weight Independent Set problem we are given a graph with a nonnegative weight function on vertices, and the goal is to find an independent set in of…
Densities in large permutations and parameter testing
Roman Glebov, Carlos Hoppen, Tereza Klimosova +3
A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permuta…
Infinite dimensional finitely forcible graphon
Roman Glebov, Tereza Klimosova, Daniel Kral
Graphons are analytic objects associated with convergent sequences of dense graphs. Finitely forcible graphons, i.e., those determined by finitely many subgraph densities, are of p…
Immersion in four-edge-connected graphs
Maria Chudnovsky, Zdeněk Dvořák, Tereza Klimošová +1
Fix g>1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g…
Finitely forcible graphons and permutons
Roman Glebov, Andrzej Grzesik, Tereza Klimosova +1
We investigate when limits of graphs (graphons) and permutations (permutons) are uniquely determined by finitely many densities of their substructures, i.e., when they are finitely…
Strong immersions and maximum degree
Zdenek Dvorak, Tereza Klimosova
A graph H is strongly immersed in G if G is obtained from H by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removal…
Hereditary properties of permutations are strongly testable
Tereza Klimosova, Daniel Kral
We show that for every hereditary permutation property P and every eps>0, there exists an integer M such that if a permutation p is eps-far from P in the Kendall's tau distance, th…