Data Structures & Algorithms Multiple Choice Questions 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
Answer: b
Clarification: 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? Answer: a 3. The number of colors used by a proper coloring graph is called? Answer: a 4. What is a chromatic number? Answer: c 5. What will be the chromatic number for an empty graph having n vertices? Answer: b 6. What will be the chromatic number for an bipartite graph having n vertices? Answer: c 7. Calculating the chromatic number of a graph is a Answer: c 8. What will be the chromatic number for a line graph having n vertices? Answer: d 9. What will be the chromatic number for a complete graph having n vertices? Answer: c 10. What will be the chromatic number for a tree having more than 1 vertex? Answer: c 11. A graph with chromatic number less than or equal to k is called? Answer: b 12. What will be the chromatic number of the following graph? Answer: b 13. What will be the chromatic number of the following graph? Answer: b 14. What will be the chromatic number of the following graph? Answer: b 15. The chromatic number of star graph with 3 vertices is greater than that of a complete graph with 3 vertices. Answer: b 16. The chromatic number of star graph with 3 vertices is greater than that of a tree with same number of vertices. Answer: b
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
Clarification: 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.
a) k coloring graph
b) x coloring graph
c) m coloring graph
d) n coloring graph
Clarification: 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.
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
Clarification: 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.
a) 0
b) 1
c) 2
d) n
View Answer
Clarification: An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.
a) 0
b) 1
c) 2
d) n
Clarification: 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.
a) P problem
b) NP hard problem
c) NP complete problem
d) cannot be identified as any of the given problem types
Clarification: 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.
a) 0
b) 1
c) 2
d) n
Clarification: 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.
a) 0
b) 1
c) n
d) n!
Clarification: 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.
a) 0
b) 1
c) 2
d) Varies with the structure and number of vertices of the tree
View Answer
Clarification: 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.
a) K chromatic
b) K colorable
c) K chromatic colorable
d) K colorable chromatic
Clarification: 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.
a) 1
b) 2
c) 3
d) 4
Clarification: 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.
a) 2
b) 3
c) 4
d) 5
View Answer
Clarification: 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.
a) 2
b) 3
c) 4
d) 5
Clarification: 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.
a) True
b) False
Clarification: 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.
a) True
b) False
Clarification: 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.