Proof of a conjecture of Plummer and Zha

DOI10.1002/JGT.22926MaRDI QIDQ6074589zbMATHOpenAlexWikidataFDO

Authors Maria Chudnovsky, Paul Seymour

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.11505

zbMATH Keywords

colouringinduced subgraphpentagraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Say a graph $G$ is a {em pentagraph} if every cycle has length at least five, and every induced cycle of odd length has length five. N. Robertson proposed the conjecture that the Petersen graph is the only pentagraph that is three-connected and internally 4-connected, but this was disproved by M. Plummer and X. Zha in 2014. Plummer and Zha conjectured that every 3-connected, internally 4-connected pentagraph is three-colourable. We prove this: indeed, we will prove that every pentagraph is three-colourable.

Recommendations

• On a conjecture concerning the Petersen graph
• On a conjecture concerning the Petersen graph. II
• Tutte's edge-colouring conjecture
• Variations on the Petersen colouring conjecture
• \(Z_3\)-connectivity of \(K_{1,3}\)-free graphs without induced cycle of length at least 5

Cites work

• A note on chromatic number and induced odd cycles
• On a conjecture concerning the Petersen graph
• On a conjecture concerning the Petersen graph. II

Cited in

(9)

• On the structure of pentagraphs
• On a conjecture concerning the Petersen graph. II
• The chromatic number of a graph with two odd holes and an odd girth
• Proof of a conjecture of Chan, Robbins, and Yuen
• Proof of the Zalcman conjecture for initial coefficients
• Graphs with girth \(2\ell+1\) and without longer odd holes that contain an odd \(K_4\)-subdivision
• Graphs with girth 9 and without longer odd holes are 3-colourable
• scientific article; zbMATH DE number 5578311 (Why is no real title available?)
• On a conjecture concerning the Petersen graph

This page was built for publication: Proof of a conjecture of Plummer and Zha

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074589)