3 added 631 characters in body

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.

2 added 1 characters in body; deleted 1 characters in body

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 graphs matrix in your decomposition. Then you immediately fall into the realm of perfect graphs.

1

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 graphs in your decomposition. Then you immediately fall into the realm of perfect graphs.