1
GATE CSE 2024 Set 2
Numerical
+2
-0.66

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ________

GATE CSE 2024 Set 2 Discrete Mathematics - Graph Theory Question 1 English

Your input ____
2
GATE CSE 2024 Set 1
MCQ (More than One Correct Answer)
+2
-0.66

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

A

$G$ contains a complete subgraph with $k$ vertices

B

$G$ contains an independent set of size at least $n/k$

C

$G$ contains at least $k(k-1)/2$ edges

D

$G$ contains a vertex of degree at least $k$

3
GATE CSE 2024 Set 1
Numerical
+2
-0.66

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ________

Your input ____
4
GATE CSE 2023
MCQ (More than One Correct Answer)
+2
-0.67

Let G be a simple, finite, undirected graph with vertex set {$$v_1,...,v_n$$}. Let $$\Delta(G)$$ denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:

for $$i=1,....,n$$

color($$v_i)$$ $$\leftarrow$$ min{$$j\in N$$ : no neighbour of $$v_i$$ is colored $$j$$}

Which of the following statements is/are TRUE?

A
This procedure results in a proper vertex coloring of G.
B
The number of colors used is at most $$\Delta(G)+1$$.
C
The number of colors used is at most $$\Delta(G)$$
D
The number of colors used is equal to the chromatic number of G.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12