@inproceedings{a9e8e73514cc4e1f952964e1b0e95705,
title = "Transversals of longest cycles in chordal and bounded tree-width graphs",
abstract = "Let lct (G) be the minimum size of a set of vertices that intersects every longest cycle of a 2-connected graph G. Let tw (G) be the tree-width of G and ω(G) be the size of a maximum clique in G. We show that lct (G) ≤ tw (G) - 1 for every G, and that lct (G) ≤ max { 1, ω(G) - 3 } if G is chordal. Those results imply as corollaries that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. We also strengthen the latter result and show that all longest cycles intersect in 2-connected graphs of tree-width at most 3, also known as partial 3-trees.",
author = "Juan Guti{\'e}rrez",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
doi = "10.1007/978-3-319-77404-6_41",
language = "English",
isbn = "9783319774039",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "558--571",
editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",
booktitle = "LATIN 2018",
}