2
$\begingroup$

Every gragh below will refer to a finite simple graph.

There is a necessary and sufficient condition for a nonempty gragh being a line gragh:

Krausz's Theorem

A nonempty gragh is a line gragh if and only if its edge set can be partitioned into a set of cliques with the property that any vertex lies in at most two cliques.

And we can find an obvious necessary condition for a nonempty gragh being a line gragh:

If a nonempty gragh $G$ is a line graph,then for any vertex $v$ of $G$,the neighbours of $v$ can be partitioned into at most two vertex sets such that the subgragh of $G$ induced by each vertex set is a clique.

I want to ask if this necessary condition is sufficient for $G$ being a line gragh.If not,please give a counterexample.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

No. The graphs you define are called "quasi-line graphs" and are a larger class than line graphs. If you search for "quasi-line graph" you will find a lot of literature on them.

The simplest counterexample is $K_{1,3}$. A larger one is a graph consisting of two copies of $K_4$ sharing one edge.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .