A note on longest paths in circular arc graphs. (English) Zbl 1317.05102

Summary: As observed by D. Rautenbach and J.-S. Sereni [SIAM J. Discrete Math. 28, No. 1, 335–341 (2014; Zbl 1293.05183)] there is a gap in the proof of the theorem of P. N. Balister et al. [Comb. Probab. Comput. 13, No. 3, 311–317 (2004; Zbl 1051.05053)], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper, we close this gap.


05C38 Paths and cycles
Full Text: DOI arXiv


[1] P.N. Balister, E. Győri, J. Lehel and R.H. Schelp, Longest paths in circular arc graphs, Combin. Probab. Comput. 13 (2004) 311-317. doi:10.1017/S0963548304006145 · Zbl 1051.05053
[2] T. Gallai, Problem 4, in: Theory of graphs, Proceedings of the Colloquium held at Tihany, Hungary, September, 1966,. P. Erdős and G. Katona Eds., Academic Press, New York-London; Akadmiai Kiad, Budapest (1968).
[3] J.M. Keil, Finding Hamiltonian circuits in interval graphs, Inform. Process. Lett. 20 (1985) 201-206. doi:10.1016/0020-0190(85)90050-X
[4] D. Rautenbach and J.-S. Sereni, Transversals of longest paths and cycles, SIAM J. Discrete Math. 28 (2014) 335-341. doi:10.1137/130910658 · Zbl 1293.05183
[5] A. Shabbira, C.T. Zamfirescu and T.I. Zamfirescu, Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1 (2013) 56-76. doi:10.5614/ejgta.2013.1.1.6 · Zbl 1306.05121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.