3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ By maximal clique, do you mean a complete subgraph not contained in a larger complete subgraph or such a subgraph of maximal size? $\endgroup$
    – Gjergji Zaimi
    Commented Feb 10, 2011 at 11:08
  • $\begingroup$ The former, I believe latter would be called "maximum clique" $\endgroup$
    – Yaroslav Bulatov
    Commented Feb 10, 2011 at 16:14

3 Answers 3

Reset to default
3
$\begingroup$

$T$ is called the clique graph of $G$, see https://link.springer.com/chapter/10.1007/0-387-22444-0_5

Improve this answer
$\endgroup$
0
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 4, 2011 at 22:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By click incidence do you mean connecting nodes whenever some clique contains them both? $\endgroup$
    – Yaroslav Bulatov
    Commented Feb 10, 2011 at 18:38
  • $\begingroup$ Thanks for this link... it may be useful for me, as I am also interested in maximal clique graphs (for different reasons). $\endgroup$
    – Andrew D. King
    Commented Feb 12, 2011 at 1:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .