Nombre chromatique de la somme cartésienne

[invite5a98f3d8]

Nombre chromatique de la somme cartésienne de deux graphes.
La somme cartésienne de deux graphes non orientés G = (VG, EG) et H = (VH , EH ) est le graphe GPH = (V, E) d ́efini par :
– V = VG × VH ;
– [(u,x),(v,y)]∈E si et seulement si u=v et [x,y]∈EH , ou [u,v]∈ EG et x=y.
a) Dessiner la somme cartésienne de deux graphes G et H de votre choix. b) On suppose que G et H sont deux graphes non vides. Montrer que
max(χ(G), χ(H )) <= χ(GPH ) <= 􏰀 χ(G) · χ(H ).


je ne sais pas d'ou commencer la question b)
Merci pour votre aide

[invite93e0873f]

Bonsoir,

Notons que le produit cartésien de graphes ressemblent beaucoup au produit cartésien des graphes vus comme ensembles : cette seconde construction produisant des « surfaces » correspondant aux produits de segments, nous les oublions afin de ne conserver qu'un objet ayant la nature d'un graphe. Ainsi, en pensant en terme du produit cartésien plus usuel, le graphe GPH est visuellement assez clair à se représenter, du moins plus qu'avec la définition abstraite que vous donnez.

Fort de cette analogie, remarquons qu'il existe des projections canoniques et . Ces projections sont telles que, par exemple, pour tout sommet , la pré-image est un graphe canoniquement isomorphes à H. Il en va de façon similaire en interchangeant les rôles de H et de G.

Du coup, si nous voulons colorier GPH, il faut déjà colorier chacune des copies de H de la forme pour ; cela donne une borne inférieure sur . Pareillement, il faut déjà colorier chacune des copies de G de la forme pour ; cela donne une autre borne inférieure sur .

Pour la borne supérieure, il suffit de colorier G avec couleurs, de colorier avec couleurs différentes, puis de colorier chaque sommet v de en utilisant « un mélange » de la couleur de et de la couleur de . Ce faisant, nous colorions GPH avec un certain nombre de couleurs (laquelle ?), ce qui donne une borne supérieure.