Recognizing -graphs – beyond circular-arc graphs

2023
book section
conference proceedings
cris.lastimport.scopus2024-04-07T17:16:32Z
dc.abstract.enIn 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph $H$, the class of $H$-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of $H$. Such classes of graphs are related to many known graph classes: for example, $K2$-graphs coincide with interval graphs, $K3$-graphs with circular-arc graphs, the union of $T$ -graphs, where $T$ ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of $H$-graphs for different graphs $H$. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a $T$ -graph, where the parameter is the size of the tree $T$ . In particular, for every fixed tree $T$ the recognition of $T$ -graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing $K3$-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph $H$ containing two distinct cycles sharing an edge, the recognition of $H$-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and P cases of $H$-graph recognition. First, we show that the recognition of $H$-graphs is NP-hard when $H$ contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing $L$-graphs, where $L$ is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of $M$ -graphs for every unicyclic graph $M$ different from a cycle and a lollipop.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.affiliationSzkoła Doktorska Nauk Ścisłych i Przyrodniczychpl
dc.conference48th International Symposium on Mathematical Foundations of Computer Sciencepl
dc.conference.cityBordoux
dc.conference.countryFrancja
dc.conference.datefinish2023-09-01
dc.conference.datestart2023-08-28
dc.conference.shortcutMFCS
dc.contributor.authorAğaoğlu Çağırıcı, Denizpl
dc.contributor.authorÇağırıcı, Onurpl
dc.contributor.authorDerbisz, Jan - 244282 pl
dc.contributor.authorHartmann, Tim A.pl
dc.contributor.authorHliněný, Petrpl
dc.contributor.authorKratochvíl, Janpl
dc.contributor.authorKrawczyk, Tomasz - 129445 pl
dc.contributor.authorZeman, Peterpl
dc.contributor.editorLeroux, Jérômepl
dc.contributor.editorLombardy, Sylvainpl
dc.contributor.editorPeleg, Davidpl
dc.date.accessioned2023-08-31T08:25:40Z
dc.date.available2023-08-31T08:25:40Z
dc.date.issued2023pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical8:1-8:14pl
dc.description.seriesLeibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber272
dc.description.versionostateczna wersja wydawcy
dc.identifier.doi10.4230/LIPIcs.MFCS.2023.8pl
dc.identifier.isbn978-3-95977-292-1pl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/318172
dc.languageengpl
dc.language.containerengpl
dc.pubinfoDagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatikpl
dc.rightsDozwolony użytek utworów chronionych*
dc.rights.licenceCC-BY
dc.rights.urihttp://ruj.uj.edu.pl/4dspace/License/copyright/licencja_copyright.pdf*
dc.share.typeinne
dc.subject.en$H$-graphspl
dc.subject.enintersection graphspl
dc.subject.enhelly propertypl
dc.subtypeConferenceProceedingspl
dc.titleRecognizing $H$-graphs – beyond circular-arc graphspl
dc.title.container48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)pl
dc.typeBookSectionpl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month