# A Note on Longest Paths in Circular Arc Graphs

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 419-426
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFelix Joos. "A Note on Longest Paths in Circular Arc Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 419-426. <http://eudml.org/doc/271225>.

@article{FelixJoos2015,

abstract = {As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.},

author = {Felix Joos},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {circular arc graphs; longest paths intersection},

language = {eng},

number = {3},

pages = {419-426},

title = {A Note on Longest Paths in Circular Arc Graphs},

url = {http://eudml.org/doc/271225},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Felix Joos

TI - A Note on Longest Paths in Circular Arc Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 419

EP - 426

AB - As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.

LA - eng

KW - circular arc graphs; longest paths intersection

UR - http://eudml.org/doc/271225

ER -

## References

top- [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[Crossref] Zbl1051.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[Crossref]
- [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[Crossref][WoS] Zbl1293.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 [Crossref] Zbl1306.05121

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.