Hadwiger et adjacence

Pas du tout pour $Hadwiger(G)$. Là ce que tu racontes, c'est la plus grosse clique qui est présente comme sous-graphe de $G$. Ce nombre est de manière évidente $\leq$ nombre chromatique de $G$.

$Hadwiger(G)$ est le nombre de sommets de la plus grosse clique qui est un mineur de $G$.

Un mineur de $G$ est un graphe que l'on peut dessiner dans $G$, c'est à dire un ensemble de parties connexes de $G$ où on décrète que 2 d'entre elles sont reliées quand elles sont disjointes et qu'une arête de $G$ les lie, c'est à dire a ses extrémités dans l'une et l'autre.

Par exemple le graphe 1-2-3-4-5-1 ne contient comme sous-graphe que des 2 cliques au plus, mais on peut y dessiner le graphe complet à 3 sommets en prenant les pays : 1==2==3; 4; 5

Si tu veux une expression en termes de "on joue avec des matrices" du nombre chromatique, c'est plus pénible. Pour les zenfants, tu peux dire les choses suit: on remplit la matrice avec 3 sortes de couleur: (u,v,vert); (u,v,rouge); (u,v,blanc) en respectant comme règle que (u,v,x) est mis dans la case ligne u, colonne v.

Le nombre chromatique est alors le plus petit entier n tel qu'en permettant des lignes et des colonnes on puisse construire une matrice diagonale par blocs avec n blocs verts (vus d'avion) et tout le reste rouge (vu d'avion).

Par "violet vu d'avion" j'entends qu'une zone ne contient que des cases violettes ou blanches.

Je ne sais pas s'il y a des moyens très simples et élégants de le faire. On peut toujours s'amuser à traduire directement mais bon...

Il faudrait peut-êrte regarder s'il y a de classiques et élégantes caractérisations des graphes connexes en termes de matriaces d'adjacence. La seule célèbre est de dire que pour toute case (non diagonale), il existe une puissance de la matrice qui rend cette case non nulle, mais bon, à part que ça fait plaisir aux gens qui aiment voir les liens entre les notions, je ne sais pas si c'est très pratique. Un coup d'oeil sur un graphe permet souvent de voir s'il est connexe ou non alors qu'un coup d'oeil sur une matrice ... :-D en tout cas moi je ne sais pas voir directement si toutes ses puissances rendront nulles telle case.

Il faut aussi additionner les voisins