Les graphes EPG ont été introduits il y a une quinzaine d'années et ont reçu une attention notable depuis. On se place sur une grille (de taille arbitraire) et chaque sommet est représenté par un chemin sur cette grille. On ajoute une arête entre ces deux sommets si leurs chemins respectifs partagent une arête. On peut montrer que tous les graphes peuvent être représentés par des graphes EPG. L'idée est alors d'étudier plus particulier le cas où les chemins sont autorisés à "tourner" seulement un nombre constant de fois. Ainsi un graphe B_k-EPG est un graphe EPG où les chemins associés à chaque sommet ne tournent qu'au plus k fois. On peut facilement montrer que les graphes B_0-EPG sont les graphes d'intervalles. Par contre, les graphes B_1-EPG sont déjà beaucoup plus compliqués. En particulier de nombreux problèmes dont la coloration, l'indépendant maximum et la domination minimum sont NP-complets.    Une classe est chi-bornée si le nombre chromatique est borné par une fonction de la clique maximum. Les classes de graphes chi-bornées ont reçu une attention notable au cours des dernières décennies. On peut facilement montrer que la classe B_1-EPG est chi-bornée et a nombre chromatique au plus 4 omega(G) (omega(G) étant la taille d'une clique maximum). Le but du stage sera d'améliorer cette borne en particulier en approchant cette question par l'axe de la dégénérescence de ces graphes.