Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 437-450 |
Number of pages | 14 |
Journal | Journal of Graph Theory |
Volume | 103 |
Issue number | 3 |
DOIs | |
State | Published - Jul 2023 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- colouring
- induced subgraph
- pentagraph