/Exposé /Talk/
La célèbre conjecture de Barnette dit que tout graphe planaire cubique 3-connexe est hamiltonien. Le nombre dichromatique d'un graphe orienté est le plus petit entier k tel que l'ensemble des sommets du graphe peut être partitionné en k ensembles induisant des graphes orientés acycliques. La conjecture de Neumann-Lara, similaire au théorème des quatre couleurs dans le cas orienté, dit que tout graphe planaire a un nombre dichromatique d'au plus 2.
Dans le but d'obtenir un renforcement commun de ces deux conjectures, on étudie les CAI-partitions. Une CAI-partition d'un graphe (orienté) est une partition de ses sommets en ensembles A et I, tels que I est un indépendant, et que A induit un sous-graphe (orienté) acyclique connexe. Trouver une CAI-partition pour certains graphes impliquerait ce renforcement commun.
On verra que tout graphe planaire orienté biparti subcubique et 2-connexe a une CAI-partition, que les conditions ne peuvent pas être relachées, et en particulier que l'on ne peut hélas pas appliquer ce résultat pour résoudre les conjectures ci-dessus.
[François Dross ] (LaBRI )
https://sites.google.com/view/francoisdross/home
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 ] .