This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Chromatic Number”.
1. What is the definition of graph according to graph theory?
a) visual representation of data
b) collection of dots and lines
c) collection of edges
d) collection of vertices
View Answer
Explanation: According to the graph theory a graph is the collection of dots and lines. Vertices are also called dots and lines are also called edges.
2. What is the condition for proper coloring of a graph?
a) two vertices having a common edge should not have same color
b) two vertices having a common edge should always have same color
c) all vertices should have a different color
d) all vertices should have same color
View Answer
Explanation: The condition for proper coloring of graph is that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.
3. The number of colors used by a proper coloring graph is called?
a) k coloring graph
b) x coloring graph
c) m coloring graph
d) n coloring graph
View Answer
Explanation: A proper graph ensures that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.
4. What is a chromatic number?
a) The maximum number of colors required for proper edge coloring of graph
b) The maximum number of colors required for proper vertex coloring of graph
c) The minimum number of colors required for proper vertex coloring of graph
d) The minimum number of colors required for proper edge coloring of graph
View Answer
Explanation: The minimum number of colors required for proper vertex coloring of graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.
5. What will be the chromatic number for an empty graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer
Explanation: An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.
6. What will be the chromatic number for an bipartite graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer
Explanation: A bipartite graph is graph such that no two vertices of the same set are adjacent to each other. So the chromatic number for such a graph will be 2.
7. Calculating the chromatic number of a graph is a
a) P problem
b) NP hard problem
c) NP complete problem
d) cannot be identified as any of the given problem types
View Answer
Explanation: Chromatic number of an arbitrary graph cannot be determined by using any convenient method. So calculating the chromatic number of a graph is an NP complete problem.
8. What will be the chromatic number for a line graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer
Explanation: A line graph of a simple graph is obtained by connecting two vertices with an edge. A line graph has a chromatic number of n.
9. What will be the chromatic number for a complete graph having n vertices?
a) 0
b) 1
c) n
d) n!
View Answer
Explanation: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. So in such a case each vertex should have a unique color. Thus the chromatic number will be n.
10. What will be the chromatic number for a tree having more than 1 vertex?
a) 0
b) 1
c) 2
d) Varies with the structure and number of vertices of the tree
View Answer
Explanation: The minimum number of colors required for proper vertex coloring of graph is called chromatic number. So every tree having more than 1 vertex is 2 chromatic.
11. A graph with chromatic number less than or equal to k is called?
a) K chromatic
b) K colorable
c) K chromatic colorable
d) K colorable chromatic
View Answer
Explanation: Any graph that has a chromatic number less than or equal to k is called k colorable. Whereas a graph with chromatic number k is called k chromatic.
12. What will be the chromatic number of the following graph?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The given graph will only require 2 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 2.
13. What will be the chromatic number of the following graph?
a) 2
b) 3
c) 4
d) 5
View Answer
Explanation: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.
14. What will be the chromatic number of the following graph?
a) 2
b) 3
c) 4
d) 5
View Answer
Explanation: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.
15. The chromatic number of star graph with 3 vertices is greater than that of a complete graph with 3 vertices.
a) True
b) False
View Answer
Explanation: The chromatic number of a star graph is always 2 (for more than 1 vertex) whereas the chromatic number of complete graph with 3 vertices will be 3. So chromatic number of complete graph will be greater.
16. The chromatic number of star graph with 3 vertices is greater than that of a tree with same number of vertices.
a) True
b) False
View Answer
Explanation: The chromatic number of a star graph and a tree is always 2 (for more than 1 vertex). So both have the same chromatic number.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Programming Books
- Apply for Computer Science Internship
- Check Design and Analysis of Algorithms Books
