3
$\begingroup$

The clique graph $C$ of a given graph $G$ has the maximal cliques of $G$ as vertices and their is an edge between two vertices in $C$ iff the corresponding cliques share some vertices.

Now for chordal graphs, this clique graph is a tree and for proper interval graphs it is a path. Incidentally for both these graphs the max-clique recognition algorithm runs in polynomial time.

My question is are there other class of graphs who has characterization in terms of its clique graph. ? I am specially looking for such characterisations for bipartite graphs.

Any link to paper/journal is welcome.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Since bipartite graphs don't contain any cliques with more than two vertices, isn't it the case that the clique graph of a bipartite graph is the same as its line graph? $\endgroup$
    – Michael Lampis
    Feb 17, 2014 at 14:04
  • 1
    $\begingroup$ There're quite a few of results in this type; however, as Michael pointed out, it doesn't make sense to discuss clique decomposition for bipartite graphs. Moreover, your definition of clique decomposition is COMPLETELY WRONG: 1) edges between disjoint cliques are allowed; 2) intersecting cliques might not have an edge. $\endgroup$
    – Yixin Cao
    Feb 17, 2014 at 15:13
  • $\begingroup$ I might have made some mistakes in understanding the definitions. But the links given in the answers been helpfull. $\endgroup$
    – Dibyayan
    Feb 17, 2014 at 17:39
  • 1
    $\begingroup$ Always if the number of maximal cliques is polynomial in the size of the graph, then finding the maximum clique can be done in polynomial time (just check each one and retain the largest). $\endgroup$
    – dspyz
    Feb 17, 2014 at 17:41
  • $\begingroup$ Something is wrong with your question statement. The sun graph (a planar graph formed by subdividing an equilateral triangle into four smaller equilateral triangles) has four maximal cliques, all of which share some vertices, so the graph you describe for it is not a tree. But the sun graph is chordal. $\endgroup$
    – David Eppstein
    Feb 18, 2014 at 22:50

2 Answers 2

Reset to default
6
$\begingroup$

I recommend you taking a look at this book chapter:

In there, many characterizations of clique graphs of specific classes are given. For example, it is mentioned that the clique graphs of chordal graphs are the dually chordal graphs and clique graphs of proper interval graphs are also proper interval graphs, and not trees and paths as you supposed.

Improve this answer
$\endgroup$
2
$\begingroup$

There are other graphs, but they are all chordal. That is, chordal graphs are precisely the class of graphs that admit a clique tree representation, see e.g. [1]. Proper interval graphs are also chordal, while bipartite graphs in general are not.

[1] Gavril, Fǎnicǎ. "The intersection graphs of subtrees in trees are exactly the chordal graphs." Journal of Combinatorial Theory, Series B 16.1 (1974): 47-56.

Improve this answer
$\endgroup$

Your Answer

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

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