8 papers
Largest planar graphs of diameter and fixed maximum degree -- connection with fractional matchings
Antoine Dailly, Sasha Darmon, Ugo Giocanti +2
The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree and diameter . In this paper, we focus on planar graphs of diameter…
Excluding an induced wheel minor in graphs without large induced stars
Mujin Choi, Claire Hilaire, Martin Milanič +1
We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer and any planar graph , the class of all $K_…
Treewidth versus clique number. V. Further connections with tree-independence number
Claire Hilaire, Martin Milanič, Đorđe Vasić
We continue the study of -bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation…
Linear colorings of graphs
Claire Hilaire, Matjaž Krnc, Martin Milanič +1
Motivated by algorithmic applications, Kun, O'Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two p…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…
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…