1
$\begingroup$

Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial time?

I suspect such a graph would have chromatic number less than or equal to $\frac{n}{2}$ if the generating set does not have order $2$ elements, because we would always find two unique elements non-adjacent to each other. Is this right? Or are there counterexamples?

Improve this question
$\endgroup$
10
  • $\begingroup$ The second claim is false: consider a complete n-partite graph with each partite having size 3. $\endgroup$
    – LeechLattice
    Commented Sep 30, 2019 at 3:59
  • $\begingroup$ @Bullet51 But, can the $n-$ partite graph be written as a cayley graph of a nilpotent group with generating set missing the elements of order $2$? $\endgroup$
    – vidyarthi
    Commented Sep 30, 2019 at 6:01
  • 1
    $\begingroup$ No, the size is nearly $18n^2$ as there are few unconnected pairs.. $\endgroup$
    – LeechLattice
    Commented Sep 30, 2019 at 10:02
  • 1
    $\begingroup$ @Bullet51My hypothesis is corrected now in the question. Edited now. $\endgroup$
    – vidyarthi
    Commented Sep 30, 2019 at 10:30
  • 1
    $\begingroup$ @Bullet51 got the size, its just $\frac{(6n)(6n-3)}{2}=18n^2-6n$ which of the order $18n^2$ $\endgroup$
    – vidyarthi
    Commented Sep 30, 2019 at 10:33

0

Reset to default

You must log in to answer this question.