2017/06/02 by Steven Chaplick, Chaplick, Steven, Peter Zeman +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1706.00575
openalex publication_date 2017/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Biró, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph H. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. We continue the study of these graph classes by considering coloring, clique, and isomorphism problems on H-graphs. We show that for any fixed H containing a certain 3-node, 6-edge multigraph as a minor that the clique problem is APX-hard on H-graphs and the isomorphism problem is isomorphism-complete. We also provide positive results on H-graphs. Namely, when H is a cactus the clique problem can be solved in polynomial time. Also, when a graph G has a Helly H-representation, the clique problem can be solved in polynomial time. Finally, we observe that one can use treewidth techniques to show that both the k-clique and list k-coloring problems are FPT on H-graphs. These FPT results apply more generally to treewidth-bounded graph classes where treewidth is bounded by a function of the clique number.