Hilton–Zhao's Core Conjecture for class 2 graphs

About 11 years old · traced to

Let GG be a simple connected graph with maximum degree Δ≥3\Delta\ge 3. The core GΔG_\Delta is the subgraph induced by the vertices of degree Δ\Delta, and Δ(GΔ)≤2\Delta(G_\Delta)\le 2. A graph is overfull if ∣E(G)∣>Δ⌊∣V(G)∣/2⌋|E(G)|>\Delta\lfloor |V(G)|/2\rfloor, and it is of class 2 when its chromatic index satisfies χ′(G)=Δ+1\chi'(G)=\Delta+1. Core Conjecture. If GG is of class 2, then GG is overfull or G=P∗G=P^*, where P∗P^* is obtained from the Petersen graph by deleting one vertex. Equivalently, every Hilton–Zhao graph G≠P∗G\ne P^* with Δ(G)≥3\Delta(G)\ge 3 is overfull. This conjecture would characterize class 2 connected graphs whose core has maximum degree at most 22, apart from the exceptional graph P∗P^*. The supplied text gives no evidence of a resolution, so its status is open.

References

Primary source

Yan Cao, Guantao Chen, Guangming Jing and Songling Shan, “Pseudo-multifan and Lollipop”, arXiv:2108.03549 (2024).

Additional references

2 papers in this index state this conjecture (2015–2021). The statement above is taken from the most recent of them; the others are arXiv:1507.05600.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.