Dark Mode

Recent questions tagged graph-coloring

0 votes

1 answer

1

Byju's graph theory coloring question
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ . The find the minimum number of colours required ot edge-colour is ?

Sahil_Lather asked in Graph Theory Apr 15

by Sahil_Lather

91 views

2 votes

0 answers

2

TIFR CSE 2023 | Part B | Question: 12
A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. It is known that the following language $\text{3COL}$ is $\text{NP}$-complete. \[ 3 \ ... $\text{(P1), (P3)}$and $\text{(P4)}$ Only problems $\text{(P1), (P2)}$and $\text{(P4)}$

admin asked in Graph Theory Mar 14

by admin

71 views

2 votes

0 answers

3

TIFR CSE 2023 | Part B | Question: 13
You have a regular tetrahedron and $4$ distinct colours. You wish to paint the faces of the tetrahedron such that each face gets a different colour. How many ways can you colour the tetrahedron? Recall that a regular tetrahedron is a three-dimensional ... considered the same if they are identical after possibly rotating the tetrahedron. $24$ $12$ $8$ $6$ $2$

admin asked in Graph Theory Mar 14

by admin

56 views

4 votes

2 answers

4

GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.

admin asked in Graph Theory Feb 15

by admin

2.5k views

3 votes

0 answers

5

graph theory
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?

Kabir5454 asked in Graph Theory Jan 2

207 views

1 vote

0 answers

6

DRDO CSE 2022 Paper 1 | Question: 10
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?

admin asked in Graph Theory Dec 15, 2022

by admin

105 views

1 vote

0 answers

7

TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable

admin asked in Graph Theory Sep 1, 2022

by admin

158 views

0 votes

0 answers

8

Best Open Video Playlist for Graph Theory: Coloring Topic | Discrete Mathematics
Please list out the best free available video playlist for Graph Theory: Coloring Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO ... ones are more likely to be selected as best. For the full list of selected videos please see here

makhdoom ghaya asked in Study Resources Aug 15, 2022

by makhdoom ghaya

82 views

2 votes

1 answer

9

TIFR CSE 2021 | Part B | Question: 13
Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in $A$, and there is an edge between two vertices if the two columns represented ... is connected. There is a clique of size $3$. The graph has a cycle of length $4$. The graph is $3$-colourable.

soujanyareddy13 asked in Graph Theory Mar 25, 2021

by soujanyareddy13

286 views

3 votes

2 answers

10

TIFR CSE 2021 | Part B | Question: 14
Consider the following greedy algorithm for colouring an $n$-vertex undirected graph $G$ with colours $c_{1}, c_{2}, \dots:$ consider the vertices of $G$ ... $m\left ( n, r \right ) = nr$ $m\left ( n, r \right ) = n\binom{r}{2}$

soujanyareddy13 asked in Graph Theory Mar 25, 2021

by soujanyareddy13

422 views

1 vote

4 answers

11

NIELIT 2017 DEC Scientist B - Section B: 52
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$

Lakshman Bhaiya asked in Graph Theory Mar 30, 2020

by Lakshman Bhaiya

2.3k views

0 votes

4 answers

12

UGC NET CSE | January 2017 | Part 2 | Question: 5
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above

go_editor asked in Graph Theory Mar 24, 2020

1.2k views

22 votes

6 answers

13

GATE CSE 2020 | Question: 52
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Arjun asked in Graph Theory Feb 12, 2020

by Arjun

9.7k views

0 votes

3 answers

14

TIFR CSE 2020 | Part B | Question: 11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$

Lakshman Bhaiya asked in Graph Theory Feb 11, 2020

by Lakshman Bhaiya

2.2k views

Page:

1
2
3
next »

Recent questions tagged graph-coloring