# Maximal clique intersection graphs

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

-
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

## 3 Answers

$T$ is called the clique graph of $G$, see http://www.springerlink.com/content/p044154345h3k7j3/.

-

Hi,

It is not an answer, just a comment. This site may be relevant: http://www.eprisner.de/Journey/CliqueGraphs.html

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.

-
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?

liliana

-
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