3
$\begingroup$

In general, The chromatic number of the clique intersection graph a graph can again be arbitrarily high. For example, take $n$ maximal cliques of size $n$ such that every pair of maximal cliques has a vertex in common.

So, for which non-trivial graphs the clique intersection graphs has bounded chromatic number even if the graph can have arbitrarily high chromatic number?

  1. Any reference to surveys in this area is welcome.

  2. I welcome any reference relating the graphs with bounded degree and to the chromatic number of its clique intersection graph.

  3. Let the independent neighborhood of a vertex $v$ in a graph is the maximum independent set with every vertex having a common neighbor as $v$. Let for a graph family $F$, we have a constant $C(F)$, such that for any graph in the family $F$, the size of independent neighborhood of a vertex $v$ in the graph is bounded by $C(F)$. Are there any studies which relate the chromatic number of the clique intersection graph family of $F$ with the above notion.

Edit:

In the clique intersection graph $C(G)$ of a graph $G$, the nodes are maximal cliques of $G$ and there is an edge whenever they share a vertex.

Note: This is different from the definition of clique-separator graph for chordal graphs (Which is a tree).

Improve this question
$\endgroup$
5
  • $\begingroup$ What exacly do you mean by clique intersection graphs? Could you include the definition in the question? $\endgroup$
    – daniello
    Dec 2, 2014 at 23:00
  • $\begingroup$ I'm confused. $K_{1,n}$ is chordal, has small chromatic number, and the intersection graph of its maximal cliques is a large complete graph. So why do you say that chordal graphs have clique intersection graphs with bounded chromatic number? $\endgroup$
    – David Eppstein
    Dec 3, 2014 at 3:13
  • $\begingroup$ A simple observation is that the degree (and hence the chromatic number) of the clique intersection graph is upper bounded by $\Delta \cdot 2^\Delta$ where $\Delta$ is max degree of $G$ $\endgroup$
    – daniello
    Dec 3, 2014 at 17:04
  • $\begingroup$ @daniello Can you please elaborate a little, May be as an answer ! $\endgroup$
    – Dibyayan
    Dec 3, 2014 at 18:33
  • $\begingroup$ Not sure if this is relevant, but anyway... There is this nice theorem that says that for any constants $x, y$, one can build a graph with girth (i.e., smallest cycle) larger than x, and the chromatic number is larger than y. In particular, in such a graph, the maximum cliques are edges, and the edges can always be colored using $2\Delta+1$ colors. No? $\endgroup$
    – Sariel Har-Peled
    Dec 4, 2014 at 5:44

2 Answers 2

Reset to default
2
$\begingroup$

For (2), any maximal clique $C$ of $G$ has size at most $\Delta+1$ and each vertex $v \in C$ participates in at most $2^{|N(v)|} \leq 2^\Delta$ maximal cliques. So the degree of $C$ in the clique intersection graph is at most $|C| \cdot 2^{|N(v)|} \leq (\Delta + 1) \cdot 2^\Delta$. Thus the clique intersection graph can be $(\Delta + 1) \cdot 2^\Delta+1$ colored.

The bound can be tightened to $(\Delta + 1) \cdot 3^{\Delta/3}+1$ by using the Moon Moser bound for the number of maximal cliques.

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

You can consider split graphs where vertices in the independent set have no common neighbor. It is easy to see that they can have large chromatic number (you can make the clique as big as you want) but their clique graphs are stars, which are bipartite.

There are no direct correlation between the chromatic number of a graph an of its clique graph. Examples are the complete bipartite graphs (small-large), paths (small-small), the previous example (large-small) and the complement of a matching (large-huge). For the last one it is possible to show that the chromatic number of the original graph is $n/2$ and the chromatic number of its clique graph is $2^{n/2-1}$.

You should also take a look at the chapter A Survey on Clique Graphs, by Jayme L. Szwarcfiter.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.