What is the chromatic number of the following graph?
some actual colouring :p
The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.
Hence minimum number of colors needed to color given graph is equal to $3$
For odd length cycles we need minimum $3$ colors for vertex coloring and for even length cycles we need just $2$.
Answer is $B$
The Four Color theorem
The chromatic number of a planar graph is no greater than four.
Using this we can rule out some option directly.
For odd length cycles we need minimum 3 colors for vertex coloring and for even length cycles we need just 2.
How is this information used to solve the given question ? Can someone elaborate on it ?
@Hemant Parihar It’s not a theorem it’s a conjecture.
@raja11sep Appel and Haken successfully delivered the proof of the Four Color Theorem in 1976, eliminating it as a conjecture being posed in the 1850s.
$chromatic\ number(\chi) \ge \frac{total\ number\ of\ vertices(n)}{Independent\ set(\alpha)}$
$n=9\ and\ \alpha=4$
$\chi = \left \lceil \frac{9}{4} \right \rceil = 3$
$and\ also$
$so\ it\ cannot\ be\ 4\ and\ answer\ is\ (b)$
R_Ayush777
yellow , green and red vertices are three independent sets here!
So 3 color used hence chromatic number =3 option B
hence, 3 colors required. so chromatic no is 3.
64.3k questions
77.9k answers
244k comments
80.0k users