Showing 2024 · math.COShow all
2 papers · 2 filters
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
On the complexity of Client-Waiter and Waiter-Client games
Valentin Gledel, Nacim Oijid, Sébastien Tavenas +1
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular after Erdos and Selfridge's first result on their connection to Ramsey theory and…