0
$\begingroup$

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \rightsquigarrow u \rightsquigarrow z$), between $x$ and $z$ (i.e., $x \rightsquigarrow u \rightsquigarrow z$), and between $x$ and $y$ (i.e., $x \rightsquigarrow u \rightsquigarrow y$).

It seems that this is impossible in a claw-free graph... Would appreciate any help with a refutation, or perhaps insights to a proof.

$\endgroup$

1 Answer 1

1
$\begingroup$

Consider the graph $G = (V,E)$ with vertex set $V=\{a,b,c,d,x,y,z,u\}$ and edge set $E=\{ac,bd,au,bu,cu,du,ax,bx,cy,dz\}$. Then, if I am not mistaken, $x,b,u,c,y$ is an induced path through $u$ between $x$ and $y$, $x,a,u,d,z$ is an induced path through $u$ between $x$ and $z$, and $y,b,u,d,z$ is an induced path through $u$ between $y$ and $z$. However, $G$ is claw-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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