Computer Sciences > Gate 2024 Set-2 > Graph
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 _________

Correct : 2

A graph is bipartite if its vertex set can be partitioned into two disjoint sets, say V1 and V2, such that every edge connects a vertex in V1 to a vertex in V2. No edges exist between vertices within the same set.

2. Determining the Chromatic Number (χ(G)):
• By definition, all vertices within V1 are completely independent of each other (not adjacent). Therefore, every vertex in V1 can safely share the exact same color (e.g., Color 1).
• Similarly, all vertices within V2 are independent of each other and can share a different color (e.g., Color 2).
• Since every edge in the graph only goes between V1 and V2, no two adjacent vertices will ever share the same color.

3. Conclusion:
Any bipartite graph containing at least one edge can be properly colored using exactly 2 colors. Therefore, its chromatic number is 2.

Similar Questions

Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v...
#280 MCQ
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph...
#314 MCQ
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
#661 Fill in the Blanks

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......