Longest Paths in Circular Arc Graphs

2013/12/11 by Felix Joos, Joos, Felix
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1312.3075

7 pages

arxiv created 2013/12/11 · openalex publication_date 2013/12/11 · arxiv updated 2013/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As observed by Rautenbach and Sereni (arXiv:1302.5503) there is a gap in the proof of the theorem of Balister et al. (Longest paths in circular arc graphs, Combin. Probab. Comput., 13, No. 3, 311-317 (2004)), which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.

Citations

• Transversals of Longest Paths and Cycles

Related

• A Tur'an-type problem for circular arc graphs
• Transversals of Longest Paths and Cycles
• A New Approach Towards a Conjecture on Intersecting Three Longest Paths
• Nonempty intersection of longest paths in 2K₂-free graphs
• Characterization of Circular-arc Graphs: III. Chordal Graphs