<p>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. </p>

<p>The bound can be tightened to  $(\Delta + 1) \cdot 3^{\Delta/3}+1$ by using the <a href="https://cstheory.stackexchange.com/questions/8390/the-number-of-cliques-in-a-graph-the-moon-and-moser-1965-result">Moon Moser bound</a> for the number of maximal cliques.</p>

CC BY-SA 3.0
2014-12-03T18:58:41.413Z
2014-12-03T19:04:56.043Z
2017-04-13T12:32:28.117Z
daniello
<p>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.</p>

<p>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}$.</p>

<p>You should also take a look at the chapter <a href="http://link.springer.com/chapter/10.1007/0-387-22444-0_5" rel="nofollow">A Survey on Clique Graphs</a>, by Jayme L. Szwarcfiter.</p>

CC BY-SA 3.0
2014-12-29T22:23:18.640Z
2014-12-29T22:23:18.640Z
Vinicius dos Santos
<p>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.</p>

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

<ol>
<li><p>Any reference to surveys in this area is welcome. </p></li>
<li><p>I welcome any reference relating the graphs with bounded degree and to the chromatic number of its clique intersection graph.</p></li>
<li><p>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.</p></li>
</ol>

<p><strong>Edit:</strong> </p>

<p>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.</p>

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

CC BY-SA 3.0
2014-12-02T23:00:26.607Z
What exacly do you mean by clique intersection graphs? Could you include the definition in the question?
daniello
CC BY-SA 3.0
2014-12-03T03:13:52.430Z
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?
David Eppstein
CC BY-SA 3.0
2014-12-03T17:04:45.530Z
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$
daniello
CC BY-SA 3.0
2014-12-03T18:33:32.517Z
@daniello Can you please elaborate a little, May be as an answer !
Dibyayan
CC BY-SA 3.0
2014-12-04T05:44:44.263Z
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?
Sariel Har-Peled
<graph-theory><graph-algorithms><graph-colouring>
Graphs whose maximal clique intersection graph has bounded chromatic number
Dibyayan
# Graphs whose maximal clique intersection graph has bounded chromatic number

(Asked by: username_0 on 2014-12-02)

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).

**Tags:** graph-theory, graph-algorithms, graph-colouring

> **Comments:**
> **username_1**: What exacly do you mean by clique intersection graphs? Could you include the definition in the question?  
> **username_2**: 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?  
> **username_1**: 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$  
> **username_0**: @username_1 Can you please elaborate a little, May be as an answer !  
> **username_3**: 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?  

---

## 2 answers

### Answer by username_1 on 2014-12-03. Score: 2 | Accepted answer

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](https://cstheory.stackexchange.com/questions/8390/the-number-of-cliques-in-a-graph-the-moon-and-moser-1965-result) for the number of maximal cliques.


---

### Answer by username_4 on 2014-12-29. Score: 2

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](http://link.springer.com/chapter/10.1007/0-387-22444-0_5), by Jayme L. Szwarcfiter.


---

