Graphes de cordes de maille au moins cinq

Louis Esperet
LABRI, Bordeaux


Résumé:

Les graphes de cordes sont définis comme les graphes d'intersection des cordes d'un cercle (je commencerai l'exposé par quelques généralités sur les graphes d'intersection). On sait que les graphes de cordes de maille cinq sont 2-dégénérés (et donc 3-liste coloriables). Dans cet exposé, on étendra ce résultat en montrant que les graphes de cordes de maille g au moins 5 contiennent une chaine de g-4 sommets de degré 2 adjacents. On donnera également une caractérisation précise de la densité de ces graphes.

Retour au séminaire