Proof of a conjecture of Plummer and Zha
Abstract
Say a graph 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 09, 2023
- Source ID
- 10.1002/jgt.22926
Entities
People
- Maria Chudnovsky
- Paul Seymour
Organizations
- Air Force Office of Scientific Research
- Princeton University