Edge Coloring Multiple Choice Questions and Answers (MCQs)

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

Answer: c
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

Answer: c
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

Answer: a
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.
advertisement
advertisement

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
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

Answer: a
Explanation: An empty graph is a graph without any edges. So the chromatic index for such a graph will be 0.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Answer: c
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

Answer: c
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.
advertisement

8. Chromatic number of line graph is always equal to the chromatic index of the graph.
a) True
b) False
View Answer

Answer: a
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

Answer: a
Explanation: A bipartite graph has an edge chromatic number equal to Δ. So bipartite graphs belongs to class 1 graphs.
advertisement

10. What will be the chromatic index of the following graph?
The chromatic index of the following graph is 2 in given diagram
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
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?
The chromatic index of the following graph is 3 in given diagram
a) 2
b) 3
c) 4
d) 5
View Answer

Answer: b
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?
The graph will require 2 unique colors so that no two incident edges have the same color
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: c
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

Answer: a
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

Answer: c
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.