Claire Hilaire
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Claire Hilaire has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Anthony Perez
Université d’Orléans
2 shared publications - Clément Dallard
Department of Informatics University of Fribourg Fribourg Switzerland
2 shared publications - Martin Milanič
University of Primorska
2 shared publications - Freddie Illingworth
Department of Mathematics University College London London UK
1 shared publication - Linda Cook
Korteweg-de Vries Institute of Mathematics, University of Amsterdam, Amsterdam, Netherlands
1 shared publication Martin Milanič
FAMNIT and IAM University of Primorska Koper Slovenia
1 shared publication
Latest Publications
- Open Access
- 8 April 2026
- Published by Wiley in Journal of Graph Theory
- Vol. 112 (3) , 337-351
Treewidth Versus Clique Number. V. Further Connections With Tree‐Independence Number
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 of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for ‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where ‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of ‐boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree‐independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.
- 8 April 2026
- Published by Wiley in Journal of Graph Theory
- Vol. 112 (3) , 337-351
Open AccessTreewidth Versus Clique Number. V. Further Connections With Tree‐Independence Number
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 of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for ‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where ‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of ‐boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree‐independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.
- 7 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Structure of graphs : minors and induced trees
Structure de graphes, mineurs et arbres induits: Cette thèse traite des questions structurelles de la théorie des graphes qui découlent de motivations algorithmiques.En effet, les problèmes de graphes NP-complets sont typiquement plus faciles dès lors qu'on restreint la classe de graphes.Sur les arbres, qui sont des graphes connexes sans cycles, la programmation dynamique donne souvent un algorithme linéaire. Tous les graphes ne sont pas des arbres, mais il est possible de quantifier à quel point un graphe est plus complexe qu'un arbre.Un outil standard pour cela est la largeur arborescente, qui est profondément liée à la théorie des mineurs, comme nous allons voir dans le premier chapitre. Une autre stratégie consiste à obtenir une structure arborescente en supprimant le moins de sommets possible, comme nous le verrons dans le deuxième chapitre.Le premier chapitre porte sur l'idée de graphes universels pour la relation de mineur.Un graphe est mineur-universel pour une famille de graphes s'il contient comme mineur chaque graphe de la famille. Un résultat célèbre de Robertson, Seymour et Thomas en 1994 montre que la grille 2n times 2n est mineur-universelle pour la famille des graphes planaires à n sommets. Une façon d'affiner ce résultat est de trouver des sous-classes de graphes planaires à n sommets qui admettent une grille mineure-universelle plus petite. On dit que qu'un graphe planaire G admet un dessin sur une grille s'il existe un plongement de G sur une grille, tel que les sommets de G sont des sommets de la grille, et ses arêtes sont des suites de segments dont les jonctions sont placées sur des sommets des la grille. La taille d'un tel dessin est le nombre de sommets de la grille. L'idée est d'établir une relation entre la taille d'un dessin sur une grille d'un graphe H, et la taille de la plus petite grille qui admet H comme mineur.Plutôt que d'affiner le résultat, un autre direction consiste à le généraliser à une classe plus grande.On s'intéresse ici aux graphes de genre borné, le genre d'un graphe étant un paramètre entier qui généralise la notion de planarité.Plus précisément, nous montrons qu'il existe un graphe de genre g mineur-universel pour les graphes à n sommets de genre g, et dont la taille est polynomiale en n et g. Le deuxième chapitre se concentre sur la recherche d'une grande forêt (union de plusieurs arbres) induite dans un graphe. Un cas intéressant est celui où la forêt en question un unique chemin. En 2017, Esperet, Lemoine et Maffray ont conjecturé que tout graphe k-dégénéré avec un chemin à n sommets admet un chemin induit à log n ^{Omega_k(1)} sommets. Nous prouvons que c'est le cas pour plusieurs classes de graphes dégénérés, y compris la classe des graphes excluant un graphe comme mineur topologique. Dans le cas d'une forêt, le théorème d'ErdH{o}s-P'osa stipule que si un graphe n'a pas k cycles disjoints, alors il admet un ensemble de O(klog k) sommets dont l'élimination produit une forêt, appelé textit{feedback vertex set}. Nous obtenons une propriété similaire pour les graphes sans sous-graphe K_{t,t} et sans k cycles indépendants (disjoints et sans arête entre eux). La contrepartie de cette généralisation est un textit{feedback vertex set} dont la taille est logarithmique en la taille du graphe, et cette borne peut être atteinte.
- 7 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Structure of graphs : minors and induced trees
Structure de graphes, mineurs et arbres induits: Cette thèse traite des questions structurelles de la théorie des graphes qui découlent de motivations algorithmiques.En effet, les problèmes de graphes NP-complets sont typiquement plus faciles dès lors qu'on restreint la classe de graphes.Sur les arbres, qui sont des graphes connexes sans cycles, la programmation dynamique donne souvent un algorithme linéaire. Tous les graphes ne sont pas des arbres, mais il est possible de quantifier à quel point un graphe est plus complexe qu'un arbre.Un outil standard pour cela est la largeur arborescente, qui est profondément liée à la théorie des mineurs, comme nous allons voir dans le premier chapitre. Une autre stratégie consiste à obtenir une structure arborescente en supprimant le moins de sommets possible, comme nous le verrons dans le deuxième chapitre.Le premier chapitre porte sur l'idée de graphes universels pour la relation de mineur.Un graphe est mineur-universel pour une famille de graphes s'il contient comme mineur chaque graphe de la famille. Un résultat célèbre de Robertson, Seymour et Thomas en 1994 montre que la grille 2n times 2n est mineur-universelle pour la famille des graphes planaires à n sommets. Une façon d'affiner ce résultat est de trouver des sous-classes de graphes planaires à n sommets qui admettent une grille mineure-universelle plus petite. On dit que qu'un graphe planaire G admet un dessin sur une grille s'il existe un plongement de G sur une grille, tel que les sommets de G sont des sommets de la grille, et ses arêtes sont des suites de segments dont les jonctions sont placées sur des sommets des la grille. La taille d'un tel dessin est le nombre de sommets de la grille. L'idée est d'établir une relation entre la taille d'un dessin sur une grille d'un graphe H, et la taille de la plus petite grille qui admet H comme mineur.Plutôt que d'affiner le résultat, un autre direction consiste à le généraliser à une classe plus grande.On s'intéresse ici aux graphes de genre borné, le genre d'un graphe étant un paramètre entier qui généralise la notion de planarité.Plus précisément, nous montrons qu'il existe un graphe de genre g mineur-universel pour les graphes à n sommets de genre g, et dont la taille est polynomiale en n et g. Le deuxième chapitre se concentre sur la recherche d'une grande forêt (union de plusieurs arbres) induite dans un graphe. Un cas intéressant est celui où la forêt en question un unique chemin. En 2017, Esperet, Lemoine et Maffray ont conjecturé que tout graphe k-dégénéré avec un chemin à n sommets admet un chemin induit à log n ^{Omega_k(1)} sommets. Nous prouvons que c'est le cas pour plusieurs classes de graphes dégénérés, y compris la classe des graphes excluant un graphe comme mineur topologique. Dans le cas d'une forêt, le théorème d'ErdH{o}s-P'osa stipule que si un graphe n'a pas k cycles disjoints, alors il admet un ensemble de O(klog k) sommets dont l'élimination produit une forêt, appelé textit{feedback vertex set}. Nous obtenons une propriété similaire pour les graphes sans sous-graphe K_{t,t} et sans k cycles indépendants (disjoints et sans arête entre eux). La contrepartie de cette généralisation est un textit{feedback vertex set} dont la taille est logarithmique en la taille du graphe, et cette borne peut être atteinte.
- 2 January 2026
- Published by Springer Nature
- p. 135-148
Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars
- 2 January 2026
- Published by Springer Nature
- p. 135-148
Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars
- 7 February 2025
- Published by Springer Nature
- p. 195-208
Sufficient Conditions for Polynomial-Time Detection of Induced Minors
- 7 February 2025
- Published by Springer Nature
- p. 195-208
Sufficient Conditions for Polynomial-Time Detection of Induced Minors
- Open Access
- 11 February 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (2) , 296-306
On tree decompositions whose trees are minors
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 by a function of the treewidth of . We prove that this is false, even when has treewidth 2 and is allowed to be a minor of .
- 11 February 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (2) , 296-306
Open AccessOn tree decompositions whose trees are minors
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 by a function of the treewidth of . We prove that this is false, even when has treewidth 2 and is allowed to be a minor of .