A claw is the graph isomorphic to $K_{1,3}$, that is, a star graph with three edges, three leaves, and one central vertex. (see below)

enter image description here

A graph is claw-free if it does not contain a claw as an induced subgraph.

The line graph of G is the intersection graph of the edges of G, that represents the adjacencies between edges of G.

A graph $F$ is a line graph if there exists a graph $H$ such that $L(H) = F$.

enter image description here

My question is why are line graphs a subclass of claw-free graphs?? Thanks a lot!

  • 2
    $\begingroup$ What have you tried? Have you tried to find a graph $H$ such that $L(H) = K_{1,3}$? There are only so many possibilities for $H$, so you should be able to try them all. What happens when you do that? $\endgroup$
    – D.W.
    Apr 10 '18 at 0:02
  • 1
    $\begingroup$ I'm confused. Even the line graph in the picture shown contains claws. $\endgroup$ Apr 10 '18 at 0:14
  • 3
    $\begingroup$ @Billiska "Claw-free" means no induced subgraphs are claws. I've edited to correct the definition in the question. $\endgroup$ Apr 10 '18 at 0:25
  • 1
    $\begingroup$ oh. never mind. induced by vertex. not induced by edge. Yes, I was going insane. thanks. $\endgroup$ Apr 10 '18 at 1:07
  • 2
    $\begingroup$ "why the former is proper subclass ". This is a different question from the one you asked originally. Please create a new question if you want to know something other than your original question. Thanks. $\endgroup$
    – Discrete lizard
    Apr 10 '18 at 9:20

Your question is answered on Wikipedia:

"Line graphs may be characterized in terms of nine forbidden subgraphs;[2] the claw is the simplest of these nine graphs."

The reference is to the following paper:

[2] Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.

Wikipedia contains a pictorial description of these nine graphs. One of them is $K_5^-$, obtained from $K_5$ by removing a single edge.

If you take any of the other forbidden subgraphs then you get a claw-free graph which isn't a line graph.

  • $\begingroup$ Thank you very much. Wow, I am a slow learner, it takes me time to understand the answer...:-) I am now working on it..... $\endgroup$
    – Pepper M
    Apr 11 '18 at 17:04

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.