<p>I recommend you taking a look at this book chapter:</p>

<ul>
<li><a href="http://link.springer.com/chapter/10.1007/0-387-22444-0_5">J. L. Szwarcfiter, <em>A Survey on Clique Graphs</em>, Recent Advances in Algorithms and Combinatorics,
CMS Books in Mathematics 2003, pp 109-136.</a></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2014-02-17T14:09:41.417Z
2014-02-17T14:09:41.417Z
Vinicius dos Santos
<p>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. </p>

<hr>

<p>[1] <a href="http://www.sciencedirect.com/science/article/pii/009589567490094X" rel="nofollow">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.</a></p>

CC BY-SA 3.0
2014-02-17T14:17:59.873Z
2014-02-17T14:17:59.873Z
Juho
<p>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.</p>

<p>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.</p>

<p>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. </p>

<p>Any link to paper/journal is welcome.</p>

CC BY-SA 3.0
2014-02-17T14:04:20.403Z
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
CC BY-SA 3.0
2014-02-17T15:13:25.500Z
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
CC BY-SA 3.0
2014-02-17T17:39:39.620Z
I might have made some mistakes in understanding the definitions. But the links given in the answers been helpfull.
Dibyayan
CC BY-SA 3.0
2014-02-17T17:41:40.913Z
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
CC BY-SA 3.0
2014-02-18T22:50:15.280Z
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
CC BY-SA 3.0
2014-02-19T03:28:06.593Z
By clique tree i was referring to the definition given by Blair,Jean RS, Barry Peyton."An introduction to chordal graphs and clique trees." Springer New York, 1993. 1-29. There theorem 3.1 gives an if and only if condition relating chordal graphs and clique trees. Again in Ibarra, Louis. "The clique-separator graph for chordal graphs." Discrete Applied Mathematics 157.8 (2009): 1737-1749 , he showed in corollary 10 clique tree for proper interval graph the clique tree is a path. I am looking for that kind of characterisation for bipartite graphs. @DavidEppstein
Dibyayan
CC BY-SA 3.0
2014-02-19T16:28:35.457Z
Ok, but then the clique tree is not the same as the intersection graph of the maximal cliques of the graph. Do you have a definition that works for non-chordal graphs?
David Eppstein
CC BY-SA 3.0
2014-02-19T17:46:29.113Z
Thank you, I think i now understand the problem in the question. Yet, I do not have a clique tree equivalent definition that would work for bipartite graphs but this certainly would be a interesting thing to explore.
Dibyayan
<graph-theory><graph-algorithms><clique>
Clique graph of bipartite graphs
Dibyayan
# Clique graph of bipartite graphs

(Asked by: username_0 on 2014-02-17)

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.

**Tags:** graph-theory, graph-algorithms, clique
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_0**: I might have made some mistakes in understanding the definitions. But the links given in the answers been helpfull.  
> **username_3**: 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).  
> **username_4**: 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.  
> **username_0**: By clique tree i was referring to the definition given by Blair,Jean RS, Barry Peyton."An introduction to chordal graphs and clique trees." Springer New York, 1993. 1-29. There theorem 3.1 gives an if and only if condition relating chordal graphs and clique trees. Again in Ibarra, Louis. "The clique-separator graph for chordal graphs." Discrete Applied Mathematics 157.8 (2009): 1737-1749 , he showed in corollary 10 clique tree for proper interval graph the clique tree is a path. I am looking for that kind of characterisation for bipartite graphs. @DavidEppstein  
> **username_4**: Ok, but then the clique tree is not the same as the intersection graph of the maximal cliques of the graph. Do you have a definition that works for non-chordal graphs?  
> **username_0**: Thank you, I think i now understand the problem in the question. Yet, I do not have a clique tree equivalent definition that would work for bipartite graphs but this certainly would be a interesting thing to explore.  

---

## 2 answers

### Answer by username_5 on 2014-02-17. Score: 6 | Accepted answer

I recommend you taking a look at this book chapter:

* [J. L. Szwarcfiter, *A Survey on Clique Graphs*, Recent Advances in Algorithms and Combinatorics,
  CMS Books in Mathematics 2003, pp 109-136.](http://link.springer.com/chapter/10.1007/0-387-22444-0_5)

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.


---

### Answer by username_6 on 2014-02-17. Score: 2

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.](http://www.sciencedirect.com/science/article/pii/009589567490094X)


---

