CHClaire Hilaire

Claire Hilaire

*This is an algorithmically generated author record based on publicly available information.

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


Claire Hilaire has a total of 15 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Treewidth Versus Clique Number. V. Further Connections With Tree‐Independence Number

    by 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 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.

  • Structure of graphs : minors and induced trees

    by Claire Hilaire

    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.

  • Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars

    by Mujin Choi, Claire Hilaire, Martin Milanič, Sebastian Wiederrecht


  • Sufficient Conditions for Polynomial-Time Detection of Induced Minors

    by Clément Dallard, Maël Dumas, Claire Hilaire, Anthony Perez


  • Detecting $K_{2,3}$ as an Induced Minor

    by Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon


  • Open Access

    On tree decompositions whose trees are minors

    by Pablo Blanco, Linda Cook, Meike Hatzel, Claire Hilaire, Freddie Illingworth, Rose McCarty

    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 .