Proof of a conjecture of Plummer and Zha

DOI10.1002/JGT.22926zbMATH Open1522.05237arXiv2201.11505OpenAlexW4313826591WikidataQ122925731 ScholiaQ122925731MaRDI QIDQ6074589FDOQ6074589

Authors: Maria Chudnovsky, Paul Seymour 

Publication date: 12 October 2023

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• Graphs with girth 9 and without longer odd holes are 3-colourable
• The chromatic number of a graph with two odd holes and an odd girth
• On a conjecture concerning the Petersen graph
• 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
• Title not available (Why is that?)

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)