MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider graph $T$ where nodes correspond to maximal cliques of some graph $G$ and two nodes can be connected if corresponding cliques intersect. Clique tree is an example when $T$ is required to be a tree and $G$ is chordal. I'm interested in graphs $T$ when tree/chordal requirements are relaxed, do they come up anywhere?

Motivation: I come across these graphs when looking at approximate decompositions of Ising model entropy, searching for "maximal clique intersection graphs" only gives me literature related to clique trees/chordal graphs

share|cite|improve this question
By maximal clique, do you mean a complete subgraph not contained in a larger complete subgraph or such a subgraph of maximal size? – Gjergji Zaimi Feb 10 '11 at 11:08
The former, I believe latter would be called "maximum clique" – Yaroslav Bulatov Feb 10 '11 at 16:14
up vote 2 down vote accepted

$T$ is called the clique graph of $G$, see

share|cite|improve this answer


It is not an answer, just a comment. This site may be relevant:

Everything changes drastically if you manage to use not clique intersection but clique incidence matrix in your decomposition. Then you immediately fall into the realm of perfect graphs.

The rows of clique-incidence matrix $A$ of a graph $G$ are incidence vectors of (maximal) cliques and vertices. For perfect graphs (that are graphs not containing induced odd cycles of the length greater than three or their complement) these matrices have several nice properties with respect to packing and covering the vertices by the subsets --- maximal cliques. Formally, the polytope $\{x : Ax\leq e, x\geq 0\}$ ($e$ is a vector of all $1$') is integral iff $G$ is perfect. In particular, a lot of NP-hard in general problems (e.g. chromatic number) are polynomial for perfect graphs. But coumting is a more subtle matter.

share|cite|improve this answer
By click incidence do you mean connecting nodes whenever some clique contains them both? – Yaroslav Bulatov Feb 10 '11 at 18:38
Thanks for this link... it may be useful for me, as I am also interested in maximal clique graphs (for different reasons). – Andrew D. King Feb 12 '11 at 1:55

Hi, I have been working with clique graphs for the last 10 years. My doctoral tesis was about clique graphs. Recently we have proved that recognizing clique graphs is an NP-complete problem. See Theoretical Computer Science Volume 410, Issues 21-23, 17 May 2009, Pages 2072-2083

What exactly do you need to know about clique graphs?


share|cite|improve this answer
I'm interested in clique graphs created by partial triangulations -- I add some chords and look at clique intersection graph where only maximal intersections form edges. The goal is to create such clique graphs where maximal intersections are almost graph separators (any cycle that goes through such set is long). I'm looking for heuristics that lets me find such triangulations while keeping maximum clique size as small as possible – Yaroslav Bulatov Mar 4 '11 at 22:25

Your Answer


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.