Register

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 5

• recategorized by
126 views

1 Answer

Best answer
2 votes
2 votes

A proper coloring of a graph is an assignment of colors to the vertices of the graph so that no two adjacent vertices have the same color.


Only $2$ colors are required.

So, the correct answer is $2.$

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
gatecse asked Sep 14, 2020
139 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 9
What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?
What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?
User Avatar
4 votes
4 votes
1 answer
2
gatecse asked Sep 14, 2020
282 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 17
What is the minimal number $k$ such that there exists a proper edge coloring (chromatic index) of the complete graph on $6$ vertices with $k$ colors?
What is the minimal number $k$ such that there exists a proper edge coloring (chromatic index) of the complete graph on $6$ vertices with $k$ colors?
User Avatar
2 votes
2 votes
1 answer
3
gatecse asked Sep 14, 2020
398 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 26
The minimum number of color required to color the complement of the below graph is ________
The minimum number of color required to color the complement of the below graph is ________
User Avatar
2 votes
2 votes
1 answer
4
gatecse asked Sep 14, 2020
249 views
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 28
The edge chromatic number of the following graph is _________
The edge chromatic number of the following graph is _________
User Avatar
Link Copied!