This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Edge Coloring”.
1. In graph theory collection of dots and lines is called
a) vertex
b) edge
c) graph
d) map
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 edge 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) No two incident edges should have the same color
d) No two incident edges should have different color
View Answer
Explanation: The condition for proper edge coloring of graph is that no two incident edges should have the same color. If it uses k colors in the process then it is called k edge coloring of graph.
3. The number of colors used by a proper edge coloring graph is called?
a) k edge coloring graph
b) x edge coloring graph
c) m edge coloring graph
d) n edge coloring graph
View Answer
Explanation: A proper edge coloring graph ensures that no two incident edges has the same color. If it uses k colors in the process then it is called k coloring of graph.
4. What is a chromatic index?
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 edge coloring of graph is called chromatic index whereas the minimum number of colors required for proper vertex coloring of graph is called chromatic number of a graph.
5. What will be the chromatic index 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 index for such a graph will be 0.
6. If chromatic number of a line graph is 4 then the chromatic index of the graph will be?
a) 0
b) 1
c) 4
d) information insufficient
View Answer
Explanation: The chromatic index of a graph is always equal to the chromatic number of its line graph. So the chromatic index of the graph will be 4.
7. Calculating the chromatic index 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 index of an arbitrary graph cannot be determined by using any convenient method. So calculating the chromatic index of a graph is an NP complete problem.
8. Chromatic number of line graph is always equal to the chromatic index of the graph.
a) True
b) False
View Answer
Explanation: The chromatic index of a graph is always equal to the chromatic number of its line graph. So we can calculate the chromatic index of a graph by calculating the chromatic number of its line graph.
9. Bipartite graph belongs to class 1 graphs.
a) True
b) False
View Answer
Explanation: A bipartite graph has an edge chromatic number equal to Δ. So bipartite graphs belongs to class 1 graphs.
10. What will be the chromatic index of the following graph?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The given graph will require 2 unique colors so that no two incident edges have the same color. So its chromatic index will be 2.
11. What will be the chromatic index 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 incident edges have the same color. So its chromatic index will be 3.
12. What will be the chromatic index of the following graph?
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The given graph will require 2 unique colors so that no two incident edges have the same color. So its chromatic index will be 2.
13. What will be the chromatic index for a complete graph having n vertices (consider n to be an odd number)?
a) n
b) n + 1
c) n – 1
d) 2n + 1
View Answer
Explanation: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. The chromatic index for an odd number of vertices will be n.
14. What will be the chromatic index for a complete graph having n vertices (consider n to be an even number)?
a) n
b) n + 1
c) n – 1
d) 2n + 1
View Answer
Explanation: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. The chromatic index for even number of vertices will be n-1.
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.
- Practice Programming MCQs
- Check Computer Science Books
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
- Check Programming Books
