When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs.

I am confused about the definition of an $S_3$ graph. I am aware that in some resources, $S_n$ means $K_{1,n}$, and in others $S_{n-1}$ means $K_{1,n}$.

However, in both cases, ($C_{n+4}$,$S_3$,claw,net)-free $\equiv$ UIG seems like a wrong notation.

If $S_3$ is $K_{1,3}$, then $S_3$ is also a claw graph. Thus, ($S_3$,claw)-free is a redundant notation. On the other hand, if $S_3$ is $K_{1,2}$, then it is wrong because a path of length 3 is realizable as a unit interval graph.

If this notation is true, then can I also write UIG $\equiv$ ($C_{n+4}$,$S_3$,$K_{1,2}$,$P_2$,claw,net)-free?
If not, then is it correct to write that UIG $\equiv$ ($C_{n+4}$,claw,net)-free?


You can look up the small graphs that ISGCI uses to define classes. Specifically, $S_3$ is the following "sun" graph:

enter image description here

ISGCI defines sun graphs as

a chordal graph on $2n$ nodes ($n\geq3$) whose vertex set can be partitioned into $W = \{w_1,\dots,w_n\}$ and $U = \{u_1, \dots,u_n\}$ such that $W$ is independent and $u_i$ is adjacent to $w_j$ iff $i=j$ or $i=j+1\pmod{n}$.

Implicitly, the subgraph induced by $U$ can be anything. Wolfram Mathworld also talks about "complete sun graphs", which is the special case where $U$ is a clique.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.