Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged graph-coloring
3
votes
4
answers
61
TIFR CSE 2016 | Part B | Question: 13
An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the following ... degree in $G$ There is a polynomial time algorithm to check if $G$ is $2$-colourable If $G$ has no triangle then it is $3$-colourable
An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we...
go_editor
1.2k
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-coloring
+
–
23
votes
2
answers
62
TIFR CSE 2017 | Part B | Question: 10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider ...
go_editor
2.7k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
37
votes
4
answers
63
TIFR CSE 2017 | Part B | Question: 1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the f...
go_editor
4.0k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
1
votes
1
answer
64
Algo-coloring
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent node gets same color?
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent nod...
srestha
664
views
srestha
asked
Dec 9, 2016
Graph Theory
graph-theory
graph-coloring
numerical-answers
+
–
1
votes
2
answers
65
GATE Overflow | Data Structures | Test 1 | Question: 19
What is the chromatic number of the following graph?
What is the chromatic number of the following graph?
Arjun
460
views
Arjun
asked
Oct 10, 2016
DS
go-ds-1
data-structures
graph-theory
graph-coloring
numerical-answers
+
–
0
votes
2
answers
66
UGC NET CSE | June 2010 | Part 2 | Question: 4
$S_{1}$ : I teach algorithms and maths. $S_{2}$ : My professor teaches maths, electronics and computer science. $S_{3}$ : I have a student of maths. $S_{4}$ : Algorithm is a part of computer science. $S_{5}$ : Maths students know computer ... amongst the entities/actors as expressed in the sentences $S_{1}$ to $S_{5}$ above ? $2$ $3$ $4$ None of these
$S_{1}$ : I teach algorithms and maths.$S_{2}$ : My professor teaches maths, electronics and computer science.$S_{3}$ : I have a student of maths.$S_{4}$ : Algorithm is a...
makhdoom ghaya
1.2k
views
makhdoom ghaya
asked
Sep 14, 2016
Graph Theory
ugcnetcse-june2010-paper2
graph-coloring
+
–
2
votes
3
answers
67
Made easy
What is the chromatic number of following graphs? 1) 2)
What is the chromatic number of following graphs?1)2)
gaurav9822
791
views
gaurav9822
asked
Aug 10, 2016
Graph Theory
graph-coloring
discrete
engineering-mathematics
+
–
1
votes
1
answer
68
Calculate chromatic number
Shiva draws a tree of N nodes, where a node can be adjacent to maximum of 4 other nodes. What is the minimum number of colors Shiva should use so that no two adjacent nodes get the same color? A. 5 B. 4 C. 3 D. 2 // Please explain how to solve this?
Shiva draws a tree of N nodes, where a node can be adjacent to maximum of 4 other nodes. What is the minimum number of colors Shiva should use so that no two adjacent nod...
sh!va
3.5k
views
sh!va
asked
Jul 12, 2016
Programming in C
algorithms
data-structures
graph-coloring
+
–
0
votes
1
answer
69
chromatic number
Imarati Gupta
1.1k
views
Imarati Gupta
asked
Jul 7, 2016
Graph Theory
graph-theory
graph-coloring
+
–
3
votes
2
answers
70
UGC NET CSE | June 2012 | Part 3 | Question: 31
The upper bound of computing time of m colouring decision problem is $O(nm)$ $O(n^m)$ $O(nm^n)$ $O(n^mm^n)$
The upper bound of computing time of m colouring decision problem is$O(nm)$$O(n^m)$$O(nm^n)$$O(n^mm^n)$
go_editor
3.0k
views
go_editor
asked
Jul 7, 2016
Programming in C
ugcnetcse-june2012-paper3
graph-theory
graph-coloring
+
–
1
votes
2
answers
71
UGC NET CSE | June 2012 | Part 2 | Question: 4
The number of colours required to properly colour the vertices of every planer graph is 2 3 4 5
The number of colours required to properly colour the vertices of every planer graph is2345
go_editor
9.6k
views
go_editor
asked
Jul 4, 2016
Graph Theory
ugcnetcse-june2012-paper2
graph-theory
graph-coloring
+
–
8
votes
2
answers
72
ISRO2007-07
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is $1$ $k$ $k-1$ $k/2$
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is$1$$k$$k-1$$k/2$
go_editor
3.9k
views
go_editor
asked
Jun 10, 2016
Graph Theory
isro2007
graph-theory
graph-coloring
+
–
1
votes
4
answers
73
IISC-CSA-Research-Test-10
A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum number of colours required for proper vertex colouring of $G$ is called the chromatic number of $G$. Then what is the chromatic number of the cycle graph on 149 vertices?
A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum num...
go_editor
776
views
go_editor
asked
Jun 8, 2016
Graph Theory
iisccsaresearch2016
descriptive
graph-theory
graph-coloring
iisc-interview
+
–
3
votes
2
answers
74
CMI2015-A-03
Suppose each edge of an undirected graph is coloured using one of three colours - red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not ... endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).
Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is t...
go_editor
570
views
go_editor
asked
May 27, 2016
Graph Theory
cmi2015
graph-theory
graph-coloring
+
–
1
votes
2
answers
75
CMI2011-B-01a
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road ... it always possible to colour each building with either red or blue so that every road connects a red and blue building?
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that:Each road connects exactly tw...
go_editor
677
views
go_editor
asked
May 19, 2016
Graph Theory
cmi2011
descriptive
graph-coloring
+
–
43
votes
4
answers
76
GATE CSE 2016 Set 2 | Question: 03
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
Akash Kanase
15.3k
views
Akash Kanase
asked
Feb 12, 2016
Graph Theory
gatecse-2016-set2
graph-theory
graph-coloring
normal
numerical-answers
+
–
17
votes
1
answer
77
Haming Distance and Chromatic Number
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “b” differ only in one bit possible (i.e., hamming distance1). What is the ratio of chromatic number of G to the diameter of G? Model Question : https://gateoverflow.in/3564/gate2006-it_25
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “...
pC
2.4k
views
pC
asked
Jan 28, 2016
Graph Theory
engineering-mathematics
algorithms
graph-coloring
+
–
26
votes
4
answers
78
TIFR CSE 2013 | Part B | Question: 1
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given di...
makhdoom ghaya
4.2k
views
makhdoom ghaya
asked
Nov 5, 2015
Graph Theory
tifr2013
graph-theory
graph-coloring
+
–
4
votes
4
answers
79
graph coloring
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
Sankaranarayanan P.N
3.0k
views
Sankaranarayanan P.N
asked
Jun 25, 2015
Graph Theory
graph-theory
graph-coloring
+
–
64
votes
9
answers
80
GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if ...
Ishrat Jahan
13.1k
views
Ishrat Jahan
asked
Oct 31, 2014
Graph Theory
gateit-2006
graph-theory
graph-coloring
normal
+
–
34
votes
4
answers
81
GATE IT 2008 | Question: 3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
What is the chromatic number of the following graph? $2$$3$$4$$5$
Ishrat Jahan
8.2k
views
Ishrat Jahan
asked
Oct 27, 2014
Graph Theory
gateit-2008
graph-theory
graph-coloring
normal
+
–
37
votes
7
answers
82
GATE CSE 2004 | Question: 77
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$
Kathleen
12.6k
views
Kathleen
asked
Sep 18, 2014
Graph Theory
gatecse-2004
graph-theory
graph-coloring
easy
+
–
46
votes
6
answers
83
GATE CSE 2002 | Question: 1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...
Kathleen
11.1k
views
Kathleen
asked
Sep 15, 2014
Graph Theory
gatecse-2002
graph-theory
graph-coloring
normal
+
–
49
votes
11
answers
84
GATE CSE 2009 | Question: 2
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$
gatecse
13.0k
views
gatecse
asked
Sep 15, 2014
Graph Theory
gatecse-2009
graph-theory
graph-coloring
normal
+
–
Page:
« prev
1
2
3
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register