Showing math.COShow all
2 papers · 1 filter
math.CO2024
A structural description of Zykov and Blanche Descartes graphs
Malory Marin, Stéphan Thomassé, Nicolas Trotignon +1
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph…
math.CO2024
Beyond recognizing well-covered graphs
Carl Feghali, Malory Marin, Rémi Watrigant
We prove a number of results related to the computational complexity of recognizing well-covered graphs. Let and be positive integers and let be a graph. Then is sa…