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
    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
    Sep 30, 2019 at 6:01
  • 1
    $\begingroup$ No, the size is nearly $18n^2$ as there are few unconnected pairs.. $\endgroup$
    – LeechLattice
    Sep 30, 2019 at 10:02
  • 1
    $\begingroup$ @Bullet51My hypothesis is corrected now in the question. Edited now. $\endgroup$
    – vidyarthi
    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
    Sep 30, 2019 at 10:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.