patternMinor
In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?
Viewed 0 times
thisdenotedfreearegraphsintervals_3clawnetaccurate
Problem
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?
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?
Solution
You can look up the small graphs that ISGCI uses to define classes. Specifically, $S_3$ is the following "sun" graph:
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.
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.
Context
StackExchange Computer Science Q#100357, answer score: 3
Revisions (0)
No revisions yet.