56 citations · 270 across the 25 of their papers we have counts for
4 papers · 1 filter
Clique-cutsets beyond chordal graphs
Valerio Boncompagni, Irena Penev, Kristina Vuskovic
Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and…
The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the…
Triangle-free graphs that do not contain an induced subdivision of are 3-colorable
Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt +3
We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic.
The (theta, wheel)-free graphs Part II: structure theorem
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole an…