3 papers
math.CO2026
On Borodin-Kostochka conjecture for correspondence coloring
ZdenÄk DvoÅák, Ross J. Kang, David MikÅ¡anÃk
Borodin and Kostochka in 1977 conjectured that if a graph has maximum degree and its clique number satisfies , then its chromatic number satisfie…
math.CO2026
Unavoidable subgraphs in digraphs with large out-degrees
Tomáš Hons, Tereza Klimošová, Gaurav Kucheriya +3
We ask the question, which oriented trees must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree. We formulate the following sim…
math.CO2026
Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio
Marthe Bonamy, ZdenÄk DvoÅák, Lukas Michel +1
We give an exact characterization of monotone graph classes C with bounded average degree that satisfy the following property: The domination number of every graph from C is bounde…