Exercice Coloriage de graphe

[Piniwini]

Bonjour, je suis en L2 informatique et je bloque sur un exercice de math qui est le suivant:
a.Trouver un graphe de nombre chromatique 4 qui n'ait aucun sous-graphe isomorphe au graphe K4
b.Trouver un graphe de nombre chromatique 5 qui n'ait aucun sous-graphe isomorphe au graphe K5

Mon problème est qu'à chaque fois que je trouve un graphe de nombre chromatique 4 il a forcement le graphe K4 en sous-graphe.

Merci d'avance.
Cordialement, Piniwini.

[Tiruxa]

Bonjour,
Pour la question a. il suffit de jouer avec la notion de cycle élémentaire d'ordre impair.

Par exemple on trace un pentagone et un prend un sommet à l'intérieur que l'on relie à chacun des sommets du pentagone.
Il n'y a pas de K4, mais on peut démontrer que le nombre chromatique est 4.

Si on colore le centre en couleur n°1, il ne reste plus qu'à colorer le tour.
Or le tour est un cycle élémentaire d'ordre impair et il faut nécessairement 3 couleurs au minimum pour colorer ce genre de cycle.
Donc en tout 4 couleurs au minimum, le nombre chromatique est 4.

Pour la b. je vais y réfléchir.

[Tiruxa]

Bon j'ai une solution qui utilise le même principe, mais cette fois on prend deux points à l'intérieur du pentagone et l'on relie ces deux points entre eux puis chacun de ces points à chacun des sommets du pentagone.
Il faut deux couleurs pour le K2 central, et ces deux couleurs ne peuvent être réutilisées pour le tour. Celui ci étant toujours un cycle élémentaire d'ordre impair, il en faut donc 3 de plus au minimum, donc 5 en tout au minimum.