Isomorphism Problem for S_d-graphs
share
An H-graph is the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H. We focus on S_d-graphs as a special case. A graph G is an S_d-graph when it is the intersection graph of connected subgraphs of a subdivision of a fixed star S_d. It is useful to mention that, for an S_d-graph G with some proper maximal clique C ∈ G, each connected component of G-C is an interval graph and the partial order on the connected components of G-C has a chain cover of size ≤ d. Considering the recognition algorithm given by Chaplick et al., we give an FPT-time algorithm to solve the isomorphism problem for S_d-graphs with bounded clique size. Then, we give a polynomial time reduction to S_d-graph isomorphism from the isomorphism problem for posets of width d. Finally, we show that the graph isomorphism problem for S_d-graphs can be solved in FPT-time with parameter d, even when the clique size is unbounded.
READ FULL TEXT