1 votes 1 votes The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________. Graph Theory gatecse2024-set2 graph-theory numerical-answers graph-coloring + – Arjun asked Feb 16 • edited Apr 24 by Arjun Arjun 2.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes The given graph is bipartite, where alternating $4$ vertices can be put in one part & remaining alternating $4$ vertices in the second part. A bipartite graph with at least $1$ edges always has chromatic number $2.$ Deepak Poonia answered Feb 16 Deepak Poonia comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The chromatic number of the given graph is $2$. Hira Thakur answered Feb 16 Hira Thakur comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Theorem - graph is bipartite $\longleftrightarrow$ graph has no odd length cycles notice that graph doesn't have any odd length cycles so graph is bipartite A bipartite graph with atleast 1 edge always has a chromatic number of 2 hence answer is 2 ssingla answered Mar 31 ssingla comment Share Follow See all 0 reply Please log in or register to add a comment.
