Nombre de Hadwiger

Un graphe avec quatre sous-graphes connectés qui, lorsqu'ils sont contractés, forment un graphe complet. Il ne possède pas de mineur complet à cinq sommets par le théorème de Wagner, donc son nombre de Hadwiger est exactement quatre.

En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K _k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G.

Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937. Les graphes qui ont un nombre de Hadwiger fini borné sont peu denses et ont aussi un petit nombre chromatique. La détermination du nombre de Hadwiger d'un graphe est NP-difficile mais traitable à paramètre fixe.

Graphes avec un petit nombre de Hadwiger

Un graphe G a un nombre de Hadwiger au plus égal à deux si et seulement s'il est une forêt, car un mineur complet à trois sommets ne peut être formé qu'en contractant un cycle de G.

Un graphe a un nombre de Hadwiger au plus trois si et seulement si sa largeur arborescente est au plus deux, ce qui est le cas si et seulement si chacune de ses composantes biconnexes est un graphe série-parallèle.

Une « somme de cliques » de deux graphes planaires et du graphe de Wagner, donnant un graphe de nombre de Hadwiger égal à quatre.

Le théorème de Wagner, qui caractérise les graphes planaires par leurs mineurs exclus, implique que les graphes planaires ont un nombre de Hadwiger au plus égal à quatre. Dans le même article où il prouve ce théorème, Wagner caractérise également les graphes avec un nombre de Hadwiger au plus égal à quatre de manière plus détaillée : ce sont des graphes qui peuvent être formés par des opérations de somme de cliques (en) qui combinent des graphes planaires avec le graphe de Wagner à huit sommets.

Les graphes avec un nombre de Hadwiger au plus cinq incluent les graphes apex (en) et les graphes plongeables sans entrelacs, qui tous deux ont le graphe complet K ₆ parmi leurs mineurs exclus.

Densité

Tout graphe avec n sommets et nombre de Hadwiger k a $O(nk{\sqrt {\log k}})$ arêtes. Cette borne est atteinte : pour tout k, il existe des graphes avec nombre de Hadwiger k et qui ont $\Omega (nk{\sqrt {\log k}})$ arêtes. Si un graphe G a un nombre de Hadwiger égal à k, alors tous ses sous-graphes ont un nombre de Hadwiger au plus égal à k, et il s'ensuit que G doit avoir une Dégénérescence en $O(k{\sqrt {\log k}})$ Par conséquent, les graphes avec un nombre de Hadwiger borné sont des graphes creux.

Coloration

La conjecture de Hadwiger affirme que le nombre de Hadwiger d'un graphe G est toujours au moins aussi grand que son nombre chromatique. Autrement dit, chaque graphe de nombre de Hadwiger k doit admettre une coloration en au plus k couleurs. Le cas k = 4 est équivalent, par la caractérisation par Wagner des graphes avec ce nombre de Hadwiger, au théorème des quatre couleurs sur les colorations des graphes planaires, et la conjecture a également été prouvée pour k ≤ 5, mais est ouverte pour des valeurs plus élevées de k.

En raison de leur faible dégénérescence, les graphes avec un nombre de Hadwiger au plus k peuvent être colorés par un algorithme de coloration glouton utilisant $O(k{\sqrt {\log k}})$ couleurs.

Complexité algorithmique

Tester si le nombre de Hadwiger d'un graphe donné est supérieur ou égal à une valeur k donnée est NP-complet, d'où il résulte que la détermination du nombre de Hadwiger est NP-difficile. Cependant, le problème est traitable à paramètre fixe : il existe un algorithme pour trouver la plus grande clique mineure dans un temps qui est polynomial en la taille du graphe, mais exponentiel en h(G). De plus, les algorithmes en temps polynomial approximent le nombre de Hadwiger de manière beaucoup plus précise que la meilleure approximation en temps polynomial (en supposant que P ≠ NP) en la taille du plus grand sous-graphe complet.

Notions associées

Le nombre achromatique d'un graphe G est la taille de la plus grande clique qui peut être formée en contractant une famille d'stable dans G.

Dans les graphes infinis, les mineurs non dénombrables peuvent être caractérisés en termes de refuges (en), qui formalisent les stratégies d'évasion pour certains jeux de poursuite-évasion (en) : si le nombre Hadwiger est non dénombrable, alors il est égal au plus grand ordre d'un refuge dans le graphe.

Tout graphe de nombre de Hadwiger k a au plus $n2^{O(k\log \log k)}$ cliques (sous-graphiques complets).

Halin a défini en 1976 une classe de paramètres de graphes qu'il appelle des fonctions S, et qui incluent le nombre de Hadwiger. Ce sont des fonctions des graphes dans les entiers doivent être nulles pour le graphe nul, être mineur-monotones, qui augmente d'une unité lorsque l'on ajoute un sommet qui est adjacent à tous les autres sommets et qui prend comme valeur la plus grande pour les deux sous-graphes situés de chaque côté d'un séparateur d'une clique. L'ensemble des toutes ces fonctions forme un treillis complet pour les opérations de minimisation et maximisation. Le plus petit élément de ce treillis est le nombre de Hadwiger, et le plus grand la largeur arborescente.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hadwiger number » (voir la liste des auteurs).

Bibliographie

• Noga Alon, Andrzej Lingas et Martin Wahlen, « Approximating the maximum clique minor and some subgraph homeomorphism problems », Theoretical Computer Science, vol. 374, n^os 1–3,‎ 2007, p. 149–158 (DOI 10.1016/j.tcs.2006.12.021, lire en ligne).
• Béla Bollobás, Paul A. Catlin et Paul Erdős, « Hadwiger's conjecture is true for almost every graph », European Journal of Combinatorics, vol. 1,‎ 1980, p. 195–199 (DOI 10.1016/s0195-6698(80)80001-1, lire en ligne).
• David Eppstein, « Finding large clique minors is hard », Journal of Graph Algorithms and Applications, vol. 13, n^o 2,‎ 2009, p. 197–204 (DOI 10.7155/jgaa.00183, arXiv 0807.0007).
• Fedor V. Fomin, Sang-il Oum et Dimitrios M. Thilikos, « Rank-width and tree-width of H-minor-free graphs », European Journal of Combinatorics, vol. 31, n^o 7,‎ 2010, p. 1617–1628 (DOI 10.1016/j.ejc.2010.05.003, arXiv 0910.0079).
• Hugo Hadwiger, « Über eine Klassifikation der Streckenkomplexe », Vierteljschr. Naturforsch. Ges. Zürich, vol. 88,‎ 1943, p. 133–143.
• Rudolf Halin, « S-functions for graphs », J. Geometry, vol. 8, n^os 1-2,‎ 1976, p. 171–186 (DOI 10.1007/BF01917434, MR 0444522).
• Alexandr V. Kostochka, « Lower bound of the Hadwiger number of graphs by their average degree », Combinatorica, vol. 4, n^o 4,‎ 1984, p. 307–316 (DOI 10.1007/BF02579141).
• Neil Robertson, Paul Seymour et Robin Thomas, « Excluding infinite minors », Discrete Mathematics, vol. 95, n^os 1-3,‎ 1991, p. 303–319 (DOI 10.1016/0012-365X(91)90343-Z, MR 1141945).
• Neil Robertson, Paul Seymour et Robin Thomas, « Hadwiger's conjecture for K₆-free graphs », Combinatorica, vol. 13, n^o 3,‎ 1993a, p. 279–361 (DOI 10.1007/BF01202354, lire en ligne).
• Neil Robertson, Paul Seymour et Robin Thomas, « Linkless embeddings of graphs in 3-space », Bulletin of the American Mathematical Society, vol. 28, n^o 1,‎ 1993b, p. 84–89 (DOI 10.1090/S0273-0979-1993-00335-5, MR 1164063, arXiv math/9301216).
• Andrew Thomason, « The extremal function for complete minors », Journal of Combinatorial Theory, vol. 81, n^o 2,‎ 2001, p. 318–338 (DOI 10.1006/jctb.2000.2013).
• Klaus Wagner, « Über eine Eigenschaft der ebenen Komplexe », Math. Ann., vol. 114,‎ 1937, p. 570–590 (DOI 10.1007/BF01594196).