|
MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEOn wheel-free graphs
par Frédéric Havet
| Date : | 06/09/11 | | Time : | 10:30 | | Location : | Lagrange Gris |
A wheel is a graph formed by a chordless cycle and a vertex that has
at least three neighbors in the cycle. We prove that every 3-connected
graph that does not contain a wheel as a subgraph is in fact minimally
3-connected. We deduce that every graph that does not contain a wheel as a subgraph is 3-colorable.
Joint work with Pierre Aboulker and N. Trotignon.
Page des séminaires
|
