Graph Coloring MCQ

1. Which of the following is not a type of graph in computer science?

a) undirected graph
b) bar graph
c) directed graph
d) weighted graph

According to graph theory, a graph is a collection of dots and lines. A bar graph is not a type of graph in computer science.

2. What is vertex coloring of a graph?

a) A condition where any two vertices having a common edge should not have the same color
b) A condition where any two vertices having a common edge should always have the same color
c) A condition where all vertices should have a different color
d) A condition where all vertices should have the same color

The condition for vertex coloring of a graph is that two vertices that 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 the graph.

3. How many edges will a tree consisting of N nodes have?

a) Log(N)
b) N
c) N – 1
d) N + 1

In order to have a fully connected tree it must have N-1 edges. So the correct answer will be N-1.

4. A Minimum number of unique colors required for vertex coloring of a graph is called?

a) vertex matching
b) chromatic index
c) chromatic number
d) color number

The minimum number of colors required for proper vertex coloring of a graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of a graph is called the chromatic index of a graph.

5. How many unique colors will be required for proper vertex coloring of an empty graph having n vertices?

a) 0
b) 1
c) 2
d) n

An empty graph is a graph without any edges. So the number of unique colors required for proper coloring of the graph will be 1.

6. How many unique colors will be required for proper vertex coloring of a bipartite graph having n vertices?

a) 0
b) 1
c) 2
d) n

A bipartite graph is a graph such that no two vertices of the same set are adjacent to each other. So the number of unique colors required for proper coloring of the graph will be 2.

7. Which of the following is an NP-complete problem?

a) Hamiltonian cycle
b) Travelling salesman problem
c) Calculating the chromatic number of a graph
d) Finding the maximum element in an array

Calculating the chromatic number of a graph is an NP-complete problem as a chromatic number of an arbitrary graph cannot be determined by using any convenient method.

8. How many unique colors will be required for proper vertex coloring of a line graph having n vertices?

a) 0
b) 1
c) 2
d) n

A line graph of a simple graph is obtained by connecting two vertices with an edge. So the number of unique colors required for proper coloring of the graph will be n.

9. How many unique colors will be required for proper vertex coloring of a complete graph having n vertices?

a) 0
b) 1
c) n
d) n!

A complete graph is one in which each vertex is directly connected with all other vertices with an edge. So the number of unique colors required for proper coloring of the graph will be n.

10. A Minimum number of colors required for proper edge coloring of a graph is called?

a) Chromatic color
b) Chromatic index
c) Edge matching
d) Color Number

The minimum number of colors required for proper edge coloring of a graph is called chromatic index. It is also known as edge chromatic number.

11. What will be the chromatic number of the following graph?

a) 1
b) 2
c) 3
d) 4

The given graph will only require 2 unique colors so that no two vertices connected by a common edge will have the same color. All nodes will have the same color except the central node.

12. How many unique colors will be required for vertex coloring of the following graph?

a) 2
b) 3
c) 4
d) 5

The given graph will require 4 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 4.

13. How many unique colors will be required for vertex coloring of the following graph

a) 2
b) 3
c) 4
d) 5

The given graph will require 3 unique colors because two diagonal vertexes are connected to each other directly. So its chromatic number will be 3.

14. Vertex coloring and chromatic numbers are one and the same.

a) True
b) False

Vertex coloring of a graph is an assignment of colors to the vertices of a graph such that no two adjacent vertices have the same color. Whereas chromatic number refers to the minimum number of unique colors required for vertex coloring of the graph.

1. What is the definition of a graph according to graph theory?

a) visual representation of data
b) collection of dots and lines
c) collection of edges
d) collection of vertices

According to graph theory, a graph is a 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?

a) two vertices having a common edge should not have the same color
b) two vertices having a common edge should always have the same color
c) all vertices should have a different color
d) all vertices should have the same color

The condition for proper coloring of a graph is that two vertices that 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 the graph.

3. The number of colors used by a proper coloring graph is called?

a) k coloring graph
b) x coloring graph
c) m coloring graph
d) n coloring graph

A proper graph ensures that two vertices that 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 the graph.

4. What is a chromatic number?

a) The maximum number of colors required for proper edge coloring of a graph
b) The maximum number of colors required for proper vertex coloring of a graph
c) The minimum number of colors required for proper vertex coloring of a graph
d) The minimum number of colors required for proper edge coloring of a graph

The minimum number of colors required for proper vertex coloring of a graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of a graph is called the chromatic index of a graph.

5. What will be the chromatic number for an empty graph having n vertices?

a) 0
b) 1
c) 2
d) n

An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.

6. What will be the chromatic number for a bipartite graph having n vertices?

a) 0
b) 1
c) 2
d) n

A bipartite graph is a 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.

7. Calculating the chromatic number 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

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

8. What will be the chromatic number for a line graph having n vertices?

a) 0
b) 1
c) 2
d) n

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.

9. What will be the chromatic number for a complete graph having n vertices?

a) 0
b) 1
c) n
d) n!

A complete graph is 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.

10. What will be the chromatic number for a tree having more than 1 vertex?

a) 0
b) 1
c) 2
d) Varies with the structure and number of vertices of the tree

The minimum number of colors required for proper vertex coloring of a graph is called chromatic number. So every tree having more than 1 vertex is 2 chromatic.

11. A graph with a chromatic number less than or equal to k is called?

a) K chromatic
b) K colorable
c) K chromatic colorable
d) K colorable chromatic

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.

12. What will be the chromatic number of the following graph?

a) 1
b) 2
c) 3
d) 4

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.

13. What will be the chromatic number of the following graph?

a) 2
b) 3
c) 4
d) 5

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.

14. What will be the chromatic number of the following graph?

a) 2
b) 3
c) 4
d) 5

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.

15. The chromatic number of a star graph with 3 vertices is greater than that of a complete graph with 3 vertices.

a) True
b) False

The chromatic number of a star graph is always 2 (for more than 1 vertex) whereas the chromatic number of a complete graph with 3 vertices will be 3. So the chromatic number of the complete graph will be greater.

16. The chromatic number of a star graph with 3 vertices is greater than that of a tree with the same number of vertices.

a) True
b) False

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.

1. In graph theory collection of dots and lines is called

a) vertex
b) edge
c) graph
d) map

According to graph theory, a graph is a 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 the same color
b) Two vertices having a common edge should always have the same color
c) No two incident edges should have the same color
d) No two incident edges should have different color

The condition for proper edge coloring of a 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 the 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

A proper edge coloring graph ensures that no two incident edges have the same color. If it uses k colors in the process then it is called k coloring of the graph.

4. What is a chromatic index?

a) The maximum number of colors required for proper edge coloring of a graph
b) The maximum number of colors required for proper vertex coloring of a graph
c) The minimum number of colors required for proper vertex coloring of a graph
d) The minimum number of colors required for proper edge coloring of a graph

The minimum number of colors required for proper edge coloring of a graph is called chromatic index whereas the minimum number of colors required for proper vertex coloring of a graph is called a 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

An empty graph is a graph without any edges. So the chromatic index for such a graph will be 0.

6. If a 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

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

The 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. A Chromatic number of a line graph is always equal to the chromatic index of the graph.

a) True
b) False

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

A bipartite graph has an edge chromatic number equal to Δ. So bipartite graphs belong 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

A complete graph is 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

A complete graph is one in which each vertex is directly connected with all other vertices with an edge. The chromatic index for an even number of vertices will be n-1.

12. What will be the chromatic index of the following graph?

a) 1
b) 2
c) 3
d) 4

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 of the following graph?

a) 2
b) 3
c) 4
d) 5

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.

14. What will be the chromatic index of the following graph?

a) 0
b) 1
c) 2
d) 3