# Clique graph of bipartite graphs

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.

• 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? Feb 17, 2014 at 14:04
• 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. Feb 17, 2014 at 15:13
• I might have made some mistakes in understanding the definitions. But the links given in the answers been helpfull. Feb 17, 2014 at 17:39
• 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). Feb 17, 2014 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. Feb 18, 2014 at 22:50