Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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? –  Michael Lampis Feb 17 at 14:04
1  
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. –  Yixin Cao Feb 17 at 15:13
    
I might have made some mistakes in understanding the definitions. But the links given in the answers been helpfull. –  Dibyayan Feb 17 at 17:39
1  
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). –  dspyz Feb 17 at 17:41
    
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. –  David Eppstein Feb 18 at 22:50

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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