Proof of a conjecture of Plummer and Zha

Maria Chudnovsky; Paul Seymour

doi:10.1002/jgt.22926

Proof of a conjecture of Plummer and Zha

Maria Chudnovsky, Paul Seymour

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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	American English
Pages (from-to)	437-450
Number of pages	14
Journal	Journal of Graph Theory
Volume	103
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22926
State	Published - Jul 2023

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

colouring
induced subgraph
pentagraph

Access to Document

10.1002/jgt.22926

Cite this

@article{6721962f653245d7a94156d8448a653d,

title = "Proof of a conjecture of Plummer and Zha",

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.",

keywords = "colouring, induced subgraph, pentagraph",

author = "Maria Chudnovsky and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2023 Wiley Periodicals LLC.",

year = "2023",

month = jul,

doi = "10.1002/jgt.22926",

language = "American English",

volume = "103",

pages = "437--450",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Proof of a conjecture of Plummer and Zha

AU - Chudnovsky, Maria

AU - Seymour, Paul

PY - 2023/7

Y1 - 2023/7

N2 - 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.

AB - 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.

KW - colouring

KW - induced subgraph

KW - pentagraph

UR - http://www.scopus.com/inward/record.url?scp=85146086525&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85146086525&partnerID=8YFLogxK

U2 - 10.1002/jgt.22926

DO - 10.1002/jgt.22926

M3 - Article

SN - 0364-9024

VL - 103

SP - 437

EP - 450

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Proof of a conjecture of Plummer and Zha

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this