14:00
15:00

The tree-independence number of a graph is the analogue of treewidth where, instead of minimising the size of bags, we minimise the size of a stable set contained in a bag. Chordal graphs have tree-independence 1, and it remains an active line of research to determine the tree-independence of various graph classes — or even to establish whether it is bounded in general. We show that graphs with no induced C4 nor P1+P4 have tree-independence at most 2 by proving a conjecture of Hilaire, Milanič, and Vasić (2025) stating that they can be made chordal by deleting a clique.

This is joint work with Marthe Bonamy and Sarah Houdaigoui.

Fanny Hauser (LaBRI)

Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

Français
LaBRI/178