Register

Recent questions tagged graph-coloring

1 votes
4 answers
31
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$
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$
User Avatar
28 votes
6 answers
33
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 _______
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...
User Avatar
1 votes
3 answers
34
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)$
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)$
User Avatar
5 votes
1 answer
36
GATE Overflow | Mock GATE | Test 1 | Question: 51
... given adjacency matrix representation of a graph containing $7$ nodes (namely A , B, C, D, E, F, G). The Chromatic number of the given graph is?
$\begin{array}{|c|c|c|c|c|c|c|} \hline 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline 1& 0 & 0 & 1 & 1 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & ...
User Avatar
4 votes
2 answers
37
Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...
User Avatar
0 votes
0 answers
39
Regular graph coloring
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
User Avatar
3 votes
1 answer
40
Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________.
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below gr...
User Avatar
0 votes
0 answers
41
How to find even or odd cylce in a graph
Consider this example , There is even vertices cycle as well as odd vertices cycle as per my understanding, let me know if it correct. Thanks a lot
Consider this example , There is even vertices cycle as well as odd vertices cycle as per my understanding, let me know if it correct.Thanks a lot
User Avatar
32 votes
5 answers
43
GATE CSE 2018 | Question: 18
The chromatic number of the following graph is _____
The chromatic number of the following graph is _____
User Avatar
8 votes
2 answers
45
MadeEasy Test Series 2018: Graph Theory - Graph Coloring
Consider the following graph: Which of the following will represents the chromatic number of the graph? answer given is 4. Please provide a detailed solution.
Consider the following graph: Which of the following will represents the chromatic number of the graph?answer given is 4.Please provide a detailed solution.
User Avatar
9 votes
1 answer
46
Graph Colouring
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
User Avatar
0 votes
0 answers
47
Test Series
Consider the following graph: Which of the following will represents the chromatic number of the graph? I think ans has to be 3 but given as 4
Consider the following graph:Which of the following will represents the chromatic number of the graph?I think ans has to be 3 but given as 4
User Avatar
1 votes
2 answers
50
#Graph theory #coloring
How to find number of ways for coloring a graph with 'm' colors for following graphs a)connected graph(with no cycles) b)regular graph
How to find number of ways for coloring a graph with 'm' colors for following graphsa)connected graph(with no cycles)b)regular graph
User Avatar
2 votes
0 answers
51
chromatic number
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
User Avatar
0 votes
0 answers
53
Chromatic polynomials
Check which of the following can be chromatic polynomials of a non-null graph ? i) x5 - 4x3 - 2x2 + x + 4 ii) x6 - 3x5 + 2x4 - 1 P.S I know for a non-null graph G, X(G) (i.e. chromatic number) is at least 2. How to proceed further ??
Check which of the following can be chromatic polynomials of a non-null graph ?i) x5 - 4x3 - 2x2 + x + 4ii) x6 - 3x5 + 2x4 - 1P.S I know for a non-null graph G, X(G) (i.e...
User Avatar
1 votes
0 answers
55
Virtual Gate Test Series: Algorithms - Tree Coloring
Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent nodes get the same color?
Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent n...
User Avatar
3 votes
3 answers
56
[Discrete Maths] Graph Theory Rosen,Chromatic number
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?
What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?
User Avatar
Page: