Say a graph (Formula presented.) is a pentagraph if every cycle has length at least five, and every induced cycle of odd length has length five. Robertson proposed the conjecture that the Petersen graph is the only internally 4-connected pentagraph, but this was disproved by Plummer and Zha in 2014. Plummer and Zha conjectured that every internally 4-connected pentagraph is three-colourable. We prove this: indeed, we will prove that every pentagraph is three-colourable.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- induced subgraph