4 papers
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin BriaÅski, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, ErdÅs conjectured that intersect…
Constricting the Computational Complexity Gap of the -Coloring Problem in -free Graphs
Justyna Jaworska, BartÅomiej Kielak, Tomáš MasaÅÃk +1
The -Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) l…
Path Eccentricity and Forbidden Induced Subgraphs
Sylwia Cichacz, Claire Hilaire, Tomáš MasaÅÃk +2
The path eccentricity of a connected graph is the minimum integer such that has a path such that every vertex is at distance at most from the path. A result of Duff…
Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
Romain Bourneuf, Jana MasaÅÃková, Wojciech Nadara +1
For a fixed integer , a (-)long claw, denoted , is the unique tree with three leaves, each at distance exactly from the vertex of degree three. Majewski…