Comptage des sous-graphes des graphes colorés à l'aide de graphes ombres

Résumé Étant donné un graphe G, le graphe de k-coloration Cₖ (G) est construit en sélectionnant les k-colorations propres de G comme sommets, avec une arête entre deux colorations si elles diffèrent dans la couleur d'exactement un sommet. Le nombre de sommets dans Cₖ (G) est le célèbre polynôme chromatique de G. Asgarli, Krehbiel, Levinson et Russell ont montré que pour tout sous-graphe H, le nombre de copies induites de H dans Cₖ (G) est une fonction polynomiale en k. Hogan, Scott, Tamitegama et Tan ont trouvé une preuve plus courte pour la polynomialité de ces H-polynômes chromatiques. Dans cet article, nous proposons une méthode pour construire ces polynômes explicitement en termes de polynômes chromatiques de graphes ombres. Nous illustrons la praticité de nos formules en calculant une formule explicite pour le H-polynôme des arbres lorsque H=Qd est un hypercube arbitraire, une tâche qui ne semble pas accessible par des méthodes précédentes. Les coefficients des polynômes résultants présentent des séquences de degrés généralisées introduites par Crew. Dans le cas particulier où H est le graphe complet sur 2 sommets, le polynôme correspondant est appelé le polynôme des paires chromatiques. Nous présentons une paire de graphes G₁ et G₂ partageant le même polynôme de paires chromatiques mais différents polynômes chromatiques, réfutant une conjecture soulevée par Asgarli, Krehbiel, Levinson et Russell.