Résumé - Problèmes de coloration des bords avec des motifs interdits et couleurs plantées

Problèmes de coloration des bords avec des motifs interdits et couleurs plantées

2025-07-25 06:59:35

{"Alexey Barsukov","Antoine Mottet","Davide Perinti"}

{cs.CC,cs.DM}

Ce document investigate les problèmes de coloration des bords avec des motifs interdits et des couleurs plantées, se concentrant sur la complexité et l'inexpressibilité de ces problèmes. Les auteurs définissent les problèmes de coloration des bords avec des motifs interdits comme ceux où l'objectif est de déterminer si les bords d'un graphe peuvent être colorés de manière à éviter certaines "obstructions". Ces obstructions sont définies par un ensemble de graphes colorés des bords, et le défi consiste à trouver une coloration qui ne permette pas la représentation de ces obstructions dans le graphe coloré. Le document fait plusieurs contributions clés : 1. **Équivalence entre problèmes de coloration et de prolongement** : Pour certains ensembles d'obstructions, les auteurs montrent qu'il existe une équivalence polynomial entre le problème de coloration (Col(F)) et le problème de prolongement (Ext(F)), où Ext(F) implique l'extension d'une coloration partielle pour éviter les obstructions. 2. **Dichotomie de complexité** : Pour des ensembles naturels d'obstructions, les auteurs établissent une dichotomie de complexité pour les problèmes de coloration des bords, ce qui signifie que de tels problèmes sont soit dans P (résolubles en temps polynomial) soit NP-complets. 3. **Résultats d'inexpressibilité** : Les auteurs investiguent la relation entre les logiques MMSNP et GMSNP, qui décrivent certaines classes de problèmes de coloration. Ils prouvent qu'il existe des familles de structures colorées des bords pour lesquelles Col(F) n'est pas égal à Col(G) pour aucune famille de structures colorées des sommets, répondant à une question ouverte dans le domaine. Le document fournit également plusieurs résultats et constructions techniques, y compris : - **Determineurs colorés** : Ce sont des graphes qui aident à prouver l'équivalence entre Col(F) et Ext(F), et l'existence de tels determineurs pour certaines familles d'obstructions. - **Gadgets d'égalité de couleur** : Ces gadgets sont utilisés pour prouver la difficulté de certains problèmes de coloration des bords. - **Problèmes de satisfaction de contraintes infinies** : Les auteurs utilisent ces problèmes pour démontrer l'équivalence entre les problèmes de coloration des bords et les problèmes de satisfaction de contraintes. Dans l'ensemble, ce document fournit une analyse complète et approfondie des problèmes de coloration des bords avec des motifs interdits et des couleurs plantées, contribuant à notre compréhension de la complexité et de l'expressibilité de ces problèmes.