Abstract
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of Hgraphs, 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, K₂graphs coincide with interval graphs, K₃graphs with circulararc graphs, the union of Tgraphs, 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 Hgraphs 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 XPalgorithm testing whether a given graph is a Tgraph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of Tgraphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃graphs (circulararc 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 Hgraphs is NPhard.
The main two results of this work narrow the gap between the NPhard and ? cases of Hgraph recognition. First, we show that the recognition of Hgraphs is NPhard when H contains two distinct cycles. On the other hand, we show a polynomialtime algorithm recognizing Lgraphs, 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 Mgraphs for every unicyclic graph M different from a cycle and a lollipop.
BibTeX  Entry
@InProceedings{agaoglucagirici_et_al:LIPIcs.MFCS.2023.8,
author = {A\u{g}ao\u{g}lu \c{C}a\u{g}{\i}r{\i}c{\i}, Deniz and \c{C}a\u{g}{\i}r{\i}c{\i}, Onur and Derbisz, Jan and Hartmann, Tim A. and Hlin\v{e}n\'{y}, Petr and Kratochv{\'\i}l, Jan and Krawczyk, Tomasz and Zeman, Peter},
title = {{Recognizing HGraphs  Beyond CircularArc Graphs}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {8:18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18542},
URN = {urn:nbn:de:0030drops185420},
doi = {10.4230/LIPIcs.MFCS.2023.8},
annote = {Keywords: Hgraphs, Intersection Graphs, Helly Property}
}
Keywords: 

Hgraphs, Intersection Graphs, Helly Property 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 