1) On note χ(G) le nombre chromatique du graphe simple G.
a) Si G = (S, A) est un graphe simple et a ∈ A montrer que
χ(G \ {a}) = χ(G) ou χ(G) − 1.
Un graphe simple G = (S, A) est spécial si
∀a ∈ A, χ(G \ {a}) = χ(G) − 1.
b) Montrer que le graphe complet Kn est spécial pour tout n.
c) Montrer que pour tout graphe simple G il existe un sous-graphe couvrant H qui est
spécial et tel que χ(H) = χ(G).
d) Montrer qu’un graphe spécial a au plus une composante connexe qui n’est pas un
point isolé.
Un graphe simple G = (S, A) est bispécial s’il est spécial et si
∀a ∈ A, G \ {a} est spécial.
e) Montrer que si un graphe spécial a plus d’une arête, il a un sommet de degré au
moins 2.
f) En déduire qu’un graphe bispécial a au plus une arête.
-----