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