Data Structures & Algorithms Multiple Choice Questions on “Edge Coloring”.
1. In graph theory collection of dots and lines is called
a) vertex
b) edge
c) graph
d) map
Answer: c
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 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: 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 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
Answer: a
Clarification: 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.
11. 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
Answer: c
Clarification: 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.