Niveau Master

Indice chromatique et théorie des graphes

Posté par
clicli 08-01-10 à 15:16

Bonjour,

L'indice chromatique $\chi '(G)$ d'un graphe G est le nombre minimal de couleurs nécessaires pour obtenir une coloration propre des arêtes d'un graphe (deux arêtes ayant un sommet en commun ne peuvent pas être de la même couleur)

Il a été démontré, dans les années soixantes, que $\Delta(G)\leq \chi '(G) \leq \Delta(G)+1$ .

Voilà ce que je cherche maintenant à prouver:

- Si G est k-régulier, et qu'il a un nombre impair de sommets, alors $\Delta(G)< \chi '(G)$ .
- Si G possède un sommet séparateur (si on supprime ce sommet et tous ses arcs incidents, alors le graphe n'est plus connexe), alors $\Delta(G)< \chi '(G)$

Voilà ce que j'ai sur la première question:

Si on a un nombre impair de sommets. alors nécessairement k est pair (puisque nb d'arêtes = $\frac{Nb~de~sommets~\times~k}{2}$ , donc le graphe est eulérien, et de là on devrait pouvoir arriver à une contradiction en supposant qu'il est coloré en k couleurs, mais je ne trouve pas trop.

Pour la deuxième question, je n'arrive même pas à dessiner un graphe qui ait un sommet séparateur!

Merci de vos aides

Posté par RE: Indice chromatique et théorie des graphes 11-01-10 à 16:16

Bon j'ai finalement réussi tout seul la question 1:

- Comme on a un nombre impair de sommets (2p+1), une couleur peut être attribuée à au plus p arêtes

- Si on utilise k couleurs on peut donc colorier au plus kp arcs.

- Or on a vu k pair, donc par exemples k=2n, donc on a en tout dans notre graphe n*(2p+1) arrêtes soit kp+n.

Avec k couleurs, un coloriage propre ne colorie donc pas toutes les arrêtes!

En revanchem je sèche toujours sur la deuxième question!