10 papers
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 p…
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…
On -Roman graphs: complexity of recognition and the case of split graphs
Kenny BeÅ¡ter Å torgel, Kenny Bešter Štorgel, Nina Chiarelli +7
For a positive integer , a -Roman dominating function of a graph is a function satisfying $\sum_{u\in N(v)} f(u) \geq…
Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
Clément Dallard, Maël Dumas, Claire Hilaire +1
The -Induced Minor Containment problem (-IMC) consists in deciding if a fixed graph is an induced minor of a graph given as input, that is, whether can be obtaine…
Induced Minor Models. I. Structural Properties and Algorithmic Consequences
Nicolas Bousquet, Clément Dallard, Maël Dumas +4
A graph is said to be an induced minor of a graph if can be obtained from by a sequence of vertex deletions and edge contractions. Equivalently, is an induced m…
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…