Proof of a conjecture of Plummer and Zha

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 languageEnglish (US)
Pages (from-to)437-450
Number of pages14
JournalJournal of Graph Theory
Issue number3
StatePublished - Jul 2023

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • colouring
  • induced subgraph
  • pentagraph


Dive into the research topics of 'Proof of a conjecture of Plummer and Zha'. Together they form a unique fingerprint.

Cite this