If $c$ is the chromatic number of $X(G)$, does $G$ contain an abelian subgroup of order $c$?

190 Views Asked by At

Let $G$ be a finite group. Define a simple graph (called the commuting graph) $X(G)$ as follows: the vertices of $X(G)$ are the elements of $G$ and two distinct vertices $x, y$ form an edge if and only if $xy=yx$.

Question: If $c$ is the chromatic number of $X(G)$, does $G$ contain an abelian subgroup of order $c$?

Notice that the existence of such a subgroup is equivalent to the existence of a complete subgraph on $c$ vertices of $X(G)$. I tried using Dirac's Theorem:

Let $c$ the chromatic number of a graph $X$. If $X$ does not contain $c$-cliques and $$T=\{x\in V(X) | d(x)>c-1\},$$ then $\sum_{x \in T} (d(x)-c+1)\geq c-3$.

1

There are 1 best solutions below

0
On

No, that is not true in general (though it would be of some interest to describe the groups for which it is).

Consider an extraspecial group $G$ of order $2^7$. The independence number $a(\Gamma)$ of $\Gamma = X(G)$ is $7$ (you can use GAP or MAGMA to check this). In general, it is true that $$a(\Gamma)\cdot\chi(\Gamma) \geq |\Gamma|,$$ where $\chi(\Gamma)$ is the chromatic number of $\Gamma$.

Thus $\chi(\Gamma) \geq 19$, whereas $2^4=16$ is the maximum order of an abelian subgroup of $G$.