کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777076 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
Biró, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a fixed graph H. They naturally generalize many important classes of graphs. We continue their study by considering coloring, clique, and isomorphism problems. We show that if H contains a certain multigraph as a minor, then H-graphs are GI-complete and the clique problem is APX-hard. Also, when H is a cactus the clique problem can be solved in polynomial time and when a graph G has a Helly H-representation, the clique problem can be solved in polynomial time. We use treewidth to show that both the k-clique and list k-coloring problems are FPT on H-graphs. These results also apply to treewidth-bounded classes where treewidth is bounded by a function of the clique number.
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 223-229