×
Joos, Felix

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

Discuss. Math., Graph Theory 35, No. 3, 419-426 (2015).
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.

Cited in 7 Documents

MSC:

05C38 Paths and cycles

Keywords:

circular arc graphs; longest paths intersection

Citations:

Zbl 1293.05183; Zbl 1051.05053
PDF BibTeX XML Cite
\textit{F. Joos}, Discuss. Math., Graph Theory 35, No. 3, 419--426 (2015; Zbl 1317.05102)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[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.