So I'm asked to find the chromatic number for the given graph by colouring the vertices using the minimum number of required colours. My attempt at doing so is below but I was wondering if someone could confirm whether I coloured it correctly? Are there any vertices that should be a different colour/should there be more or less colours used? Did I misplace any colours?

I was also wondering if there is some rule or formula to figure out the chromatic number for a graph?

I'd appreciate some help or confirmation.

Link to graph: https://imgur.com/a/1UVydLo

  • 1
    $\begingroup$ You shouldn't include a link to an image. Rather the image directly itself. You link point to a website, using cookies and collecting data, that we may not want to go to. Furtermore, a direct image is safer for future reference $\endgroup$ – Thomas Lesgourgues Jun 10 at 7:45

Nodes $8, 14, 15$ form a triangle. Therefore it is not possible to color the graph with less than $3$ colors. Since you used $3$ colors and no two adjacent nodes have the same color, your coloring is correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.