Testbook Logo
Exams SuperCoaching Test Series Skill Academy
More

Question

Download Solution PDF

The chromatic number of the following graph is _______.

5a9624d82bb8d71065f0b66c 16424163985521

This question was previously asked in
GATE CS 2018 Official Paper
Download PDF Attempt Online
View all GATE CS Papers >

Answer (Detailed Solution Below) 3
Free Tests
View all Free tests >
Free
GATE CS Full Mock Test
5.3 K Users
65 Questions 100 Marks 180 Mins
Start Now

Detailed Solution

Download Solution PDF

Concept:

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color 

Start coloring from the highest degree vertex and be stringent with the number of new colors.

Analysis:-

In this case, 3 colors are sufficient in properly coloring the graph.

5a9624d82bb8d71065f0b66c 16424163985582
hence, 3 colors required to color the above graph.

Download Solution PDF
Latest GATE CS Updates

Last updated on Jan 8, 2025

-> GATE CS 2025 Admit Card has been released on 7th January 2025.

-> The exam will be conducted on 1st February 2025 in 2 shifts.

-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.

-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.

-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.

More Colouring Questions

Q1.Consider the following statements: (A) Any tree is 2-colorable (B) A graph G has no cycles of even length if it is bipartite. (C) A graph G is 2-colorable if is bipartite (D) A graph G can be colored with d + 1 colors if d is the maximum degree of any vertex in the graph G. (E) A graph G can be colored with O(log |v|) colors if it has O(|v|) edges. Choose the correct answer from the options given below:
Q2.Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is ______.
Q3.The minimum number of colours that is sufficient to vertex-colour any planar graph is_______. 

More Graph Theory Questions

Q1.Which of the following statements is/are TRUE for undirected graphs?
Q2.Which of the following graphs are trees ?  A.  B.  C.  D.  Choose the correct answer from the options given below :  
Q3.Statement 1: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover. Statement 2: The lower bound can be found by maximizing the following \(\rm\sum_{v \in V}^n {w}(v) {x}(v)\) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V x(v) ≤ 1 for each v ∈ V x(v) ≥ 0 for each v ∈ V In the light of the above statements, choose the most appropriate answer from the options given below:
Q4.Match List I with List II LIST - I LIST - II A. Planar Graph I. Probabilistic Model B. Bipartite Graph II. Deterministic Model C. PERT III. 4-Colorable D. CPM IV. 2-Colorable Choose the correct answer from the options given below:
Q5.Consider the following statements: P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges. Q: All vertices of Euler graph are of even degree. R: Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one. S: There exits a bipartite graph with more than ten vertices which is 2-colorable. What is the number of correct statements among the above statements.
Q6.A principal node is a
Q7.A star connected network consumes a power of 20 kW with a power factor of 0.8. Calculate the value of resistance of each coil when a supply voltage of 230 volts and 50 Hz is supplied between two phases of the network.
Q8.Which of the following properties of the circuits of a graph are correct? 1. The minimum number of branches possible in a circuit will be equal to the number of elements in a circuit. 2. There are exactly two paths between any pair of vertices in a circuit. 3. There are at least two branches in a circuit. Select the correct answer using the code given below.
Q9.A path is a particular subgraph consisting of an ordered sequence of branches having which of the following properties? 1. At all but two of its nodes, called internal nodes, there are incident exactly two branches of the subgraph. 2. At each of the remaining two nodes, called terminal nodes, there is incident exactly one branch of the subgraph. Select the correct answer using the code given below.
Q10.Given below are two statements Statement I : In an undirected graph, number of odd degree vertices is even. Statement II : In an undirected graph, sum of degrees of all vertices is even. In light of the above statements, choose the correct answer from the options given below.
Crack GATE CSE with
India's Super Teachers
Explore Supercoaching For FREE
Suggested Test Series
View All >
ISRO Scientist Computer Science Mock Test
22 Total Tests with 1 Free Tests
Start Free Test
GATE Mathematics & General Aptitude (Common for All) Test Series
92 Total Tests with   0 Free Tests
Start Free Test
Suggested Exams
Exam-Logo
GATE CS

GATE CS Important Links

More Engineering Mathematics Questions

Q1.If L = {1, 2, 3, 4, 6, 9, 36} is the lattice find the number of complements 9 is having in the below given Hasse diagram?
Q2.Which of the following statements is/are TRUE for undirected graphs?
Q3.A flip-flop is used to store the ____________.
Q4.Let \(\rm \begin{pmatrix}2&a\\\ b&c\end{pmatrix}\) be a 2 x 2 real matrix for which 6 is an eigenvalue. Which of the following statements is necessarily true?
Q5.If the value of the approximate solution of the initial value problem   \(\rm \left\{\begin{matrix}y'(x)=x(y(x)+1), &x\in R\\\ y(0)=β \end{matrix}\right.\) at x = 0.2 using the forward Euler method with step size 0.1 is 1.02, then the value of β is 
Q6.The system of linear equations 3x – 2y – kz = 10 2x – 4y – 2z = 6 x + 2y – z = 5m is inconsistent if :
Q7.The statement among the following that is a tautology is:
Q8.The logical statement (p ⇒ q) ∧ (q ⇒∼ p) is equivalent to
Q9.An unbiased coin is tossed 5 times. Suppose that a variable X is assigned the value k when k consecutive heads are obtained for k = 3, 4, 5, otherwise 𝑋 takes the value -1. The expected value of X, is
Q10.For the statements p and q, consider the following compound statements: (a) (~q∧(p → q)) → ~p (b) ((p∨q))∧~p) → q Then which of the following statements is correct?
Important Links for GATE Exam
Super Coaching
Branch wise Page
Test Series
Previous Year Papers
Testbook Edu Solutions Pvt. Ltd.
1st & 2nd Floor, Zion Building,
Plot No. 273, Sector 10, Kharghar,
Navi Mumbai - 410210
[email protected]
Toll Free:1800 833 0800
Office Hours: 10 AM to 7 PM (all 7 days)
Company
About usCareers We are hiringTeach Online on TestbookPartnersMediaSitemap
Products
Test SeriesTestbook PassOnline CoursesOnline VideosPracticeBlogRefer & EarnBooks
Our Apps
Follow us on
Copyright © 2014-2022 Testbook Edu Solutions Pvt. Ltd.: All rights reserved
User PolicyTermsPrivacy
Hot Links： teen patti winner teen patti cash teen patti master apk download