Lundi 14:
Les slides sur le dechargement.
Le papier qui introduit la coloration acyclique par liste.
(vu en cours avec 3 couleurs, le papier traite aussi 4 et 5 couleurs, avec le MAD).
Le papier sur la coloration d'aretes par liste (vu en cours).
La borne de 59 pour la coloration orientee des planaires sans triangles (vu en cours).
Le papier qui introduit le maximum average degree
avec application pour la coloration orientee.
La borne de 40 pour la coloration orientee des planaires sans triangles.
Lundi 21:
Ca sera votre tour de bosser: entrainement et exos sur du dechargement.
La page wikipedia sur la probabilistic_method.
Sujet de stage:
La coloration injective est telle que pour tout sommet v, les voisins de v ont des couleurs differentes (deux sommets adjacents pouvant avoir la meme couleur).
Le sujet porte plus precisement sur la coloration injective avec 3 couleurs. Les graphes coloriables ont donc un degre maximum au plus 3.
On obtient facilement que les graphes planaires de maille au moins 21 sont coloriables.
On peut construire un graphe planaire non-coloriable de maille 10 en utilisant des resultats de 3-coloration d'aretes des graphes planaires cubiques.
L'etudiant devra tenter de reduire cet ecart entre 10 et 21. On essayera aussi de tranformer les resultats de non-coloration en resultats de NP-completude.
Le sujet pourra etre etendu a un plus grand nombre de couleurs et d'autres classes de graphes.