Les problèmes en combinatoire sont souvent formulés de la manière suivante: “Est-il vrai qu’un objet X satisfait la propriété Y?”. Lorsque la réponse est “oui”, l’informaticien aime avoir ce qu’il nomme un “certificat”. Par exemple, si la question est de savoir si un graphe G admet une 3-coloration, un tel certificat peut être une bonne 3-coloration. En revanche, dans le cas où la réponse est négative, la notion de certificat demeure floue. Comment certifier qu’un certain graphe n’est pas 3-coloriable? Existe-t-il une raison évidente pour laquelle un autre graphe n’a pas de couplage parfait? Dans cette thèse de doctorat, nous introduisons de nouveaux concepts afin de certifier la non k-colorabilité de certaines classes de graphes. Etant donnés un graphe G et un entier positif k, nous introduisons le graphe ZkG dans lequel il existe toujours un certificat canonique de non k-colorabilité pour G (et pour ZkG) dès lors que G n’est pas k-coloriable. Ces graphes, que nous avons nommés power graphs ont de bonnes propriétés que nous avons étudiées. En particulier, il existe un lien entre ces power graphs et la façon classique d’exprimer la coloriabilité avec des polynômes multivariés et le théorème
des zéros du Hilbert (Nullstellensatz).
De plus, nous avons découvert une nouvelle méthode pour prouver des résultats de coloriablité qui utilise des objets qui apparaissent naturellement dans le monde des power graphs: les precolorings. Bien que cette méthode soit délicate à appliquer en pratique, elle semble très prometteuse. En particulier, nous avons fait une nouvelle preuve de la fameuse “cycle + triangles” conjecture d’Erdös.
En étudiant les precolorings, nous avons également découvert un lien avec la transformée de Fourier discrète. Cet outil constitue un moyen efficace de créer des precolorings dans le but d’appliquer notre méthode.
Gratuit
Disciplines