0
$\begingroup$

Is the chromatic number of a Cayley graph on $p$-groups with any generating set bounded by the chromatic number of the maximal induced circulant subgraph?

I think yes. Because for one, the main obstruction to the chromatic number, the clique size directly corresponds to a circulant subgraph. For another probable reason, from this question, it appears that some circulant graphs' coloring can be extended to those for Cayley graphs on $p$-groups using homomorphism extension. Is a similar extension possible for any other Cayley graph with respect to some generating set? Any hints? Thanks beforehand.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What is "the maximal induced circulant subgraph"? How does clique size "directly correspond" to a circulant subgraph? $\endgroup$
    – verret
    Commented Jan 9, 2022 at 3:27
  • $\begingroup$ @verret I regard the largest set of vertices (along with the corresponding edges) whose induced graph with respect to the generating set is a circulant graph as the "maximal induced circulant graph" $\endgroup$
    – vidyarthi
    Commented Jan 9, 2022 at 10:30
  • $\begingroup$ @verret Since a clique is a circulant graph, so I say that clique "directly correspond" to a circulant subgraph. Of course, I am interested in the case the clique is not the one consisting of all vertices of the graph $\endgroup$
    – vidyarthi
    Commented Jan 9, 2022 at 10:32

1 Answer 1

Reset to default
1
$\begingroup$

First, if you mean the largest induced circulant subgraph, you should call it a maximum induced circulant subgraph, not maximal. (That is quite standard in this kind of area, where maximal would mean "not contained in a larger one".)

Second, "the" maximal (or maximum) induced circulant subgraph is generally not well-defined. One could have multiple maximum induced circulant subgraphs that are not isomorphic, or don't even have the same chromatic number.

Third, contrary to what is claimed in the other question you linked to, maximum induced circulant subgraphs typically do not correspond to cyclic subgroups, or to any natural substructure of the original group.

Even if they did correspond to cyclic subgroups, why would that imply the relationship between chromatic numbers? All in all, there is really no reason for anything close to this to be true. (And why the restriction to $p$-groups?)

Anyway, if one goes looking for counter-example, it's hard not to find one. One must of course avoid order $p$, as these graphs are all circulants. So one goes to order $p^2$. $p=2$ is degenerate here, as all Cayley graphs of order $4$ are circulants, but one can take $p=3$ and consider for example $C_3\square C_3$, the Cartesian product of two $3$-cycles (one of the simplest Cayley graph that is not a circulant).

If one removes a (maximum/maximal) independent set of size $3$, the induced subgraph on the remaining six vertices is a $6$-cycle, which is a circulant. It is not too hard to check that there are no other induced circulant subgraphs of order at least $6$. A $6$-cycle has chromatic number $2$, but the original graph has chromatic number $3$.

(Note that $6$ does not divide $9$, so this also illustrates the non-correspondence with subgroups.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .