8 citations · 8 across the 12 of their papers we have counts for
16 papers
On -Roman graphs: complexity of recognition and the case of split graphs
Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández +4
For a positive integer , a -Roman dominating function of a graph is a function satisfying $\sum_{u\in N(v)} f(u) \geq…
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…
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…
Treewidth versus clique number: induced minors
Claire Hilaire, Martin Milanič, Nicolas Trotignon +1
We prove that a hereditary class of graphs is -bounded if and only if the induced minors of the graphs from the class form a -bounded class.
Path eccentricity of -AT-free graphs and application on graphs with the consecutive ones property
Paul Bastide, Claire Hilaire, Eileen Robinson
The central path problem is a variation on the single facility location problem. The aim is to find, in a given connected graph , a path minimizing its eccentricity, which i…
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…
Minor-Universal Graph for Graphs on Surfaces
Cyril Gavoille, Claire Hilaire
We show that for integer every and every surface , there is a graph embeddable on with at most vertices that contains as a minor every -vertex graph embeddabl…
On tree decompositions whose trees are minors
Pablo Blanco, Linda Cook, Meike Hatzel +3
In 2019, Dvořák asked whether every connected graph has a tree decomposition so that is a subgraph of and the width of is bounded…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
Long induced paths in minor-closed graph classes and beyond
Claire Hilaire, Jean-Florent Raymond
In this paper we show that every graph of pathwidth less than that has a path of order also has an induced path of order at least . This is an exponent…
On the proper interval completion problem within some chordal subclasses
François Dross, Claire Hilaire, Ivo Koch +4
Given a property (graph class) , a graph , and an integer , the \emph{-completion} problem consists in deciding whether we can turn into a graph with the property $…