The max-clique chromatic number of a graph

Question

Let $G = (V,E)$ be a graph. Every clique, that is, complete subgraph, is contained in a maximal clique with respect to $\subseteq$ (this is an easy consequence of Zorn's Lemma). Let $\newcommand{\MC}{\text{MaxCliq}(G)}\MC$ denote the collection of all maximal cliques of $G$.

The max-clique chromatic number of $G$, denoted by $\chi_m(G)$ is defined to be the chromatic number of the hypergraph $(V(G), \MC)$. Clearly, for every graph $G$ we have $\chi_m(G) \leq \chi(G)$, as every vertex coloring in the graph sense is a coloring in the hypergraph sense.

Note that if $G$ is a triangle-free graph, then $\chi_m(G) = \chi(G)$. On the other hand, for every complete graph $K$ we have $\chi_m(K) = 2$.

Question. Given any integer $n>2$, is there a graph $G$ with $|C| \geq n$ for all $C \in \MC$ and $\chi_m(G) = \chi(G)$?

Answer 1

The answer is yes if infinite graphs are allowed.

Theorem. For any integer $n\ge3$ there is an infinite graph $G=(V,E)$ such that $\chi_m(G)=\chi(G)=\aleph_0$, and every maximal clique of $G$ has cardinality $n$ or $\aleph_0$.

Proof. Let $V=\binom{\mathbb N}{n-1}$, the set of all $(n-1)$-element subsets of $\mathbb N$, and let $E=\{x,y\}\in\binom V2:|x\cup y|=n\}$.

Observe that the maximal cliques of $G$ are the sets of the form $\{x\in V:x\subseteq A\}$ where $A\in\binom{\mathbb N}n$ and the sets of the form $\{x\in V:B\subseteq x\}$ where $B\in\binom{\mathbb N}{n-2}$.

Plainly $\chi_m(G)\le\chi(G)\le\aleph_0$. On the other hand, by Ramsey's theorem, for any coloring of $V$ with finitely many colors there will be a monochromatic maximal clique of the form $\{x\in V:x\subseteq A\}$ where $A\in\binom{\mathbb N}n$. Hence $\chi_m(G)=\chi(G)=\aleph_0$.

Answer 2

If $\chi(G)$ is finite, and all maximal cliques have size at least 3, you may take a graph coloring and unite two colors. This gives a proper coloring of the maximal cliques hypergraph with strictly less than $\chi(G)$ colors.

Answer 3

Fedor Petrov, in a comment on my previous answer, asked whether there is a countable graph in which every maximal clique is infinite, and the hypergraph of maximal cliques has infinite chromatic number. I claim that the Rado graph (the random countable graph) is such a graph.

Recall that the Rado graph is the (unique up to isomorphism) graph on $\aleph_0$ vertices with the property that, if $X$ and $Y$ are any two disjoint finite sets of vertices, then there is a vertex $v\notin X\cup Y$ which is joined to every vertex in $X$ but to no vertex in $Y$; it follows that there are infinitely many such vertices. Of course every maximal clique of the Rado graph is infinite.

Theorem. Let $G=(V,E)$ be the Rado graph. For any $n\in\mathbb N$ and any vertex coloring $V=C_1\cup\cdots\cup C_n$ there is a monochromatic maximal clique.

Proof. First let me define some notation.

Definition. If $X$ and $Y$ are disjoint finite subsets of $V$, then $R(X,Y)$ is the (infinite) set of all vertices in $V\setminus(X\cup Y)$ which are joined to every vertex in $X$ but to no vertex in $Y$.

Definition. For $i\in[n]$ an $i$-block is a finite (possibly empty) clique $B\subseteq C_i$ for which there is a vertex $u\in V\setminus C_i$ such that $R(B,\{u\})\cap C_i$ is finite.

We consider two cases.

Case 1. For each $i\in[n]$ there is an infinite sequence of pairwise disjoint $i$-blocks; in other words, for every finite set $S\subseteq V$, there is an $i$-block $B\subseteq V\setminus S$.

For each $i$-block $B$ choose a vertex $u_{i,B}\in V\setminus C_i$ such that $R(B,\{u_{i,B}\})\cap C_i$ is finite.

For each $i\in[n]$ we can choose pairwise disjoint $i$-blocks $B(i,k)$ for $1\le k\le i$ which are also disjoint from $\{u_{j,B(j,h)}:i\lt j\le n,\ 1\le h\le j\}$.

Next, for each $i\in[n]$, we can choose $B_i\in\{B(i,k):1\le k\le i$ so that $u_{j,B_j}\notin B_i$ for $1\le j\lt i$.

Now $X=B_1\cup\cdots\cup B_n$ and $Y=\{u_{1,B_1},\dots,u_{n,B_n}\}$ are disjoint finite subsets of $V$, so $R(X,Y)$ is infinite, but $R(X,Y)\cap C_i\subseteq R(B_i,\{u_{i,B_i}\})\cap C_i$ is finite for each $i\in[n]$, which is absurd. So this case cannot occur.

Case 2. For some $i\in[n]$ there is no infinite sequence of pairwise disjoint $i$-blocks.

We may assume that $i=1$ and that $V\setminus C_1\ne\varnothing$. Choose a finite set $S\subseteq V$ so that $V\setminus S$ contains no $1$-block, and let $V\setminus C_1=\{u_i:i\in\mathbb N\}$.

Now we can choose vertices $w_1,w_2,\dots$ so that $w_k\in R(\{w_1,\dots,w_{k-1}\},\{u_k\})\cap(C_1\setminus S)$ for each $k\in\mathbb N$. For suppose $w_1,\dots,w_{k-1}$ have been chosen accordingly. Then the set $\{w_1,\dots,w_{k-1}\}\subseteq C_1\setminus S$ is a clique, but it is not a $1$-block (being disjoint from $S$), so we can choose a vertex $w_k\in R(\{w_1,\dots,w_{k-1}\},\{u_k\})\cap(C_1\setminus S)$.

Finally, extend the infinite clique $\{w_1,w_2,\dots\}$ to a maximal clique $W$; then $W\subseteq C_1$ since $W$ can't contain any of the vertices $u_k$.