5-colorabilité des graphes
(1,2)-composés.
Un graphe G est dit k-dégénéré, si on peut indexer ses sommets x1,··· ,xn de
telle manière que chaque xi possède au plus k voisins dans G parmi
{x1;x2;···;xi-1}.
Cette définition est équivalente à la suivante:
Un graphe G est dit k-dégénéré, si tout sous-graphe de G possède un sommet de
degré inférieur ou égal à k.
On dit qu'un graphe G est (m1, m2,··· ,ms)-composé, si E(G) se partitionne en E1,
··· ,Es tels que pour tout
1=<j=<s, le sous-graphe
engendré par Ej est
mj-dégénéré.
Exemples: les graphes 1-dégénérés sont les forêts. Les graphes planaires sont
5-dégénérés. Les graphes outerplanar (planaires, dont les sommets peuvent
être disposés sur un cercle) sont 2-dégénérés.
Les graphes k dégénérés sont intéressants, car on peut les
k+1-colorer par un algorithme glouton.
Conjecture 1 [N. Tarsi]
Tout graphe (1,2)-composé est 5 colorable.
Clairement, tout graphe (1,2)-composé est 6 colorable puisque c'est
l'union d'un graphe 2-colorable et d'un graphe 3-colorable.
J'ai montré que la conjecture suivante implique la conjecture de
Tarsi:
Conjecture 2 [F.
Havet] Tout graphe G
(1,2)-composé si pout toute arête e
de G, il existe une (1,2)
décomposition (T,H) de
G telle que e appartienne à
T.
Cette conjecture est impliquée par
la conjecture plus forte suivante:
Conjecture 3 [F.
Havet] Tout graphe G
(1,2)-composé est l'union de trois
arbres Ti, pour i=1,2,3
tels que G-Ti est un graphe
2-dégénéré.
Remarquons que tout
graphe 2-dégénéré se décompose trivialement
en deux arbres T1 et T2. En effet, pour chaque xi de la suite (x1, x2,... ,
xn), il y a au plus deux arêtes
e1=xixj1 et e2=xixj2 avec j1<i et j2<i. Il suffit de mettre e1 dans T1 et
e2 dans T2.
J'ai testé cette dernière
conjecture par ordinateur et n'ai pas trouvé de contrexemple.
Donner une preuve constructive de la conjecture de Tarsi
aurait aussi un grand intérêt. Cela permettrait de donner un algorithme
simple pour 5-colorer une classes de graphes qui contient les graphes
planaires d'après le théorème suivant:
Théorème 1 [B.
Jackson] Tout graphe planaire est
(1,2)-composé.
Le preuve de ce théorè est disponible dans le compte-rendu
de la session de problème du 09 avril 1997