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 satisfies $…
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…
math.CO2025
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…