5
$\begingroup$

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)$?

$\endgroup$
3
  • $\begingroup$ Right - will correct $\endgroup$ Commented Dec 2, 2024 at 15:27
  • $\begingroup$ For the inequality $\chi_m(G) \leq \chi(G)$ you are assuming that $G$ has no isolated vertices, right? $\endgroup$ Commented Dec 2, 2024 at 17:08
  • $\begingroup$ @bof he defines hypergraph proper coloring so that each edge of size at least 2 is monochromatic, see the link $\endgroup$ Commented Dec 3, 2024 at 2:38

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Very nice example. Is it possible to construct a graph with countable many vertices so that works for $n=\omega$, i.e., every maximal clique is infinite and the hypergraph of maximal cliques is not properly colorable with finitely many colors? $\endgroup$ Commented Dec 3, 2024 at 6:17
  • $\begingroup$ I may be wrong but I think I've proved that the Rado graph works, see my new answer. $\endgroup$ Commented Dec 9, 2024 at 9:11
5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ That works if the chromatic number is finite. Does the question make sense if the chromatic number can be an infinite cardinal number? $\endgroup$ Commented Dec 2, 2024 at 17:14
  • $\begingroup$ @bof sorry, I always read "graph" as a "finite graph". Interesting question, not clear immediatly $\endgroup$ Commented Dec 2, 2024 at 18:46
  • 2
    $\begingroup$ Well, the OP cites Zorn's lemma for the existence of maximal cliques, which must be overkill if only finite graphs are intended! $\endgroup$ Commented Dec 3, 2024 at 3:18
2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ looks fine with me $\endgroup$ Commented Dec 9, 2024 at 9:34
  • $\begingroup$ Thanks! for looking at it! $\endgroup$ Commented Dec 9, 2024 at 9:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.