Isomorphism Problem for S_d-Graphs

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 \in 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 $\leq 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.