Homomorphismes de graphes signés – HOSIGRA

Ce projet est axé sur le développement de la théorie des homomorphismes de graphes signés dont l'étude a débuté en 2010, dans le cadre d'un séjour postdoctoral de Reza Naserasr encadré par Éric Sopena. Cette théorie trouve ses motivations dans plusieurs extensions du théorème des quatre couleurs : la conjecture de Hadwiger, l'une de ses extensions (connue sous le nom de "odd-Hadwiger conjecture"), les conjectures de Naserasr et Guenin (sur les homomorphismes de graphes planaires vers les cubes projectifs), et deux conjectures de Seymour (sur l'index chromatique des graphes planaires et sur la caractérisation des "binary clutters").

Un graphe signé est un graphe dont les arêtes sont équipées d'un signe, positif ou négatif. Cette particularité permet de définir une notion fine de mineur, où seules les arêtes positives peuvent être contractées, mais où les signes des arêtes incidentes à un même sommet peuvent être inversés simultanément. Ainsi, alors que la classe des graphes ne possédant pas de triangle comme mineur correspond à la classe des forêts, la classe des graphes signés totalement négatifs (dont toutes les arêtes sont négatives) ne possédant pas de triangle totalement négatif comme mineur correspond à la classe des graphes bipartis totalement négatifs. Ainsi, alors que cette propriété assure dans les deux cas la 2-colorabilité des graphes correspondants, la famille concernée dans le cas signé correspond exactement à la famille des graphes 2-colorables (et constitue de ce fait une caractérisation). L'un des principaux objectifs de ce projet est de tirer parti de cet avantage dans un cadre plus large en se basant sur la notion d'homomorphisme de graphes signés.

Une question particulièrement intéressante est celle des homomorphismes vers les cubes projectifs signés. Ces graphes sont obtenus à partir des hypercubes en ajoutant une arête négative entre chaque paire de sommets antipodaux. L'existence d'un homomorphisme d'un graphe signé vers un cube projectif signé est équivalente à un problème de "packing" des arêtes des graphes considérés. Une importante question concerne l'étude des homomorphismes des graphes planaires (signés) vers les cubes projectifs (signés). Cette question est une extension directe du théorème des quatre couleurs, et est reliée à l'étude des nombres chromatiques circulaire et fractionnaire des graphes planaires de maille impaire donnée. Il existe également une forte connexion avec la détermination de l'index chromatique des multigraphes planaires réguliers.

D'un point de vue algorithmique, une preuve de la conjecture de dichotomie de Feder et Vardi a récemment été obtenue en caractérisant les digraphes pour lesquels le problème d'existence d'un homomorphisme dont ils sont la cible était polynomial. Pouvoir étendre ces travaux au cas des digraphes signés serait un résultat particulièrement intéressant.