Cycles in 3‐connected claw‐free planar graphs and 4‐connected planar graphs without 4‐cycles
Journal of Graph Theory · 2024-12 · 107 (4) · 702-728
DOI: 10.1002/jgt.23152 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 21.07.2024. Verfasst von On‐Hei Solomon Lo. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 20 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, Japan Society for the Promotion of Science.
Abstract (Originalsprache)
The cycle spectrum of a graph is the set of the cycle lengths in . Let be a graph class. For any integer , define to be the least integer such that for any with circumference at least . Denote by , and the classes of 3‐connected planar graphs, 3‐connected cubic planar graphs, 3‐connected claw‐free planar graphs, and 3‐connected claw‐free cubic planar graphs, respectively. The values of and were known for all . In the first part of this article, we prove the claw‐free version of these results by giving the values of and for all . In the second part we study the cycle spectra of 4‐connected planar graphs without 4‐cycles. Bondy conjectured that every 4‐connected planar graph has all cycle lengths from 3 to except possibly one even length. The truth of this conjecture would imply that every 4‐connected planar graph without 4‐cycles has all cycle lengths other than 4. It was already known that . We prove that can be embedded in the plane such that for any has a ‐cycle and all vertices not in lie in the exterior of .
Förderung
- Natural Sciences and Engineering Research Council of Canada
- Japan Society for the Promotion of Science
Zitieren
APA
Lo, O. S. (2024). Cycles in 3‐connected claw‐free planar graphs and 4‐connected planar graphs without 4‐cycles. Journal of Graph Theory, 107(4), 702-728. https://doi.org/10.1002/jgt.23152
Vancouver
Lo OS. Cycles in 3‐connected claw‐free planar graphs and 4‐connected planar graphs without 4‐cycles. Journal of Graph Theory. 2024;107(4):702-728. doi:10.1002/jgt.23152
BibTeX
@article{Lo2024,
author = {Lo, On‐Hei Solomon},
title = {Cycles in 3‐connected claw‐free planar graphs and 4‐connected planar graphs without 4‐cycles},
journal = {Journal of Graph Theory},
year = {2024},
volume = {107},
number = {4},
pages = {702--728},
doi = {10.1002/jgt.23152}
}
EUVIMED