OpenAlex ·
Restricting Odd Antiholes in Critical Graphs via List Coloring
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.14241
- Original
- Read it at the publisher
- Topics
Abstract
By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antiholes in critical graphs with fixed maximum degree. We prove that if $G$ is a $k$-critical graph with maximum degree $Δ$ then every odd antihole in $G$ has length at most $2(Δ-k)+7$, and conjecture that, in the odd-hole-free setting, equality forces the graph itself to be the corresponding odd antihole. We verify this extremal characterization when $Δ\geq 2k-5$, extending recent results for $Δ=k$, and construct $k$-critical odd-hole-free graphs showing that the next possible odd antihole length $2(Δ-k)+5$ below the extremal bound can occur. Our proofs use a list-coloring theorem for graphs on $2\ell-1$ vertices whose complements are hypomatchable. This motivates the conjecture that every odd antihole $\overline{C_{2\ell-1}}$ is strongly $\ell$-chromatic-choosable; we show that this conjecture would imply the full extremal characterization. We also obtain degree and attachment restrictions for odd antiholes in critical graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach
Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
Polynomial directed treewidth forces a large bramble with congestion two
FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.