Théorie des graphes
Bonjour,
je m'intéresse depuis peu à la conjecture de Hadwiger chère à Christophe et plus généralement à la théorie des graphes. Voici une question que je me suis posée en buvant mon thé : soit $G$ un graphe connexe de nombre chromatique $k$. Soient $C_1, C_2,...C_k$ les $k$ couleurs utilisées pour effectuer un coloriage de $G$. Définissons le $C_k$-degré $d_{k}(x)$ d'un sommet $x$ de $G$ comme le nombre d'arêtes $[x,y]$ telles que $y$ est de couleur $C_k$. A-t-on pour tout $i\ne j$ $\displaystyle{\sum_{\substack{x \ \ sommet \\ de \ \ couleur \ \ C_{i}}}d_{j}(x)=\sum_{\substack{x \ \ sommet \\ de \ \ couleur \ \ C_{j}}}d_{i}(x)}$ ?
Merci d'avance.
je m'intéresse depuis peu à la conjecture de Hadwiger chère à Christophe et plus généralement à la théorie des graphes. Voici une question que je me suis posée en buvant mon thé : soit $G$ un graphe connexe de nombre chromatique $k$. Soient $C_1, C_2,...C_k$ les $k$ couleurs utilisées pour effectuer un coloriage de $G$. Définissons le $C_k$-degré $d_{k}(x)$ d'un sommet $x$ de $G$ comme le nombre d'arêtes $[x,y]$ telles que $y$ est de couleur $C_k$. A-t-on pour tout $i\ne j$ $\displaystyle{\sum_{\substack{x \ \ sommet \\ de \ \ couleur \ \ C_{i}}}d_{j}(x)=\sum_{\substack{x \ \ sommet \\ de \ \ couleur \ \ C_{j}}}d_{i}(x)}$ ?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Eu sinon désolé, il y a des calculs*** et comme tu sais, c'est dangereux pour moi de les lire, mais vraiment je t'aurais bien aidé.
***D'ailleurs à cause de ça, je n'ai jamais pu profiter de la preuve que la evasive conjecture est vraie pour les graphes qui ont un cardinal qui est un nombre premier :-(
Le vert-degré du premier sommet violet est 1, celui du deuxième est 1, celui du troisième est 1. Donc dans le sens violet->vert : 1+1+1=3.
De même dans le sens rouge->violet : 2+2+1=5, et dans le sens violet-rouge :1+2+2=5.
Dans le sens rouge->bleu : 0+0+2=2, et dans le sens bleu->rouge : 0+2+0=2.
Dans le sens rouge->vert : 2+1+1=4, et dans le sens vert->rouge : 1+2+1=4.
Dans le sens vert->bleu : 2+0+1=3, et dans le sens bleu->vert : 0+1+2=3.
Dans le sens violet->bleu : 1+1+1=3, et dans le sens bleu-violet : 2+1+0=3.
Dans le graphe de la figure du lien du post précédent, les couleurs absentes du premier sous-graphe connexe de $G$ sont le violet et le bleu, les couleurs absentes du deuxième sous-graphe connexe de $G$ sont le bleu et le vert, les couleurs absentes du troisième sous-graphe connexe de $G$ sont le vert et le violet, les couleurs absentes du quatrième et dernier sous-graphe de $G$ sont le violet et le rouge.
Associons à $G'_i$ la couleur absente de $G'_i$ mais pas de $G'_{i+1}$ (avec $G'_{k+1}=G'_{1}$) : on a $C_1=violet$, $C_2=bleu$, $C_3=vert$, $C_4=rouge$.
Ah oui, bien vu.
un graphe G non 17 coloriable est un cas particulier de tautologie. Toutes les tautologies sont des cas particuliers d'évidences. En aprticulier dans le cas des graphes, l'évidence E "au dessus" serait un graphe H plus difficile de manière évidente à colorier que G et en même temps plus difficile à Hadwigerrer que G. Le caractère évident se traduirait par le fait qu'il est évident que H n'est pas 17 coloriable (pas seulement vrai)
Mais il y aurait un lemme qui dirait que tous les graphes dont il est évident qu'ils sont non 17-coloriables seraient 18-contractables, ce qui entrainerait que G le serait et donc Hadwiger. Je donne l'idée à la ronde car je fais le pari que le jour où on prouvera Hadwiger ce sera par ce procédé.
Peut-être y a-t-il moyen d'utiliser le fait que toute application continue d'un espace connexe vers $\{0,1\}$ est constante, et de remplacer $0$ et $1$ par $C_{i}$ et $\{C_{j}, j\ne i\}$ pour chaque sous-graphe connexe $G'_{i}$ si on arrive à montrer que l'application qui à un sommet de $G'_i$ associe sa couleur est continue ?
En fait, si je t'avais répondu dans la seconde en MP c'est parce que c'était la première idée qui m'était venu quand j'avais pris connaissance d'Hadwiger.. Et Pourquoi elle m'était venue? Parce que l'énoncé "mon oui en MP" =>"Hadwiger" a une forme logique qui est en fait une généralisation presque mécanique de Brouwer dans le sens que c'est de la forme "il existe X blabla => il existe X connexe blabla", dont Brouwer est un cas particulier. Avec du travail il est possible aussi que cete idée marche... L'avenir dira peut-être.
sans trop savoir pourquoi, je viens de repenser à Hadwiger. Je me demande s'il n'existerait pas un automorphisme de $G$ qui enverrait un ensemble de sommets de même couleur $C_k$ vers $G'_k$. Qu'en penses-tu Christophe ?