The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions tagged graphcoloring
+3
votes
0
answers
1
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 ... D with also blue which is other than Green, now this case is clearly violating graph coloring property. How, to solve this one?
asked
Jan 22
in
Graph Theory
by
Shubhanshu
Veteran
(
15.8k
points)

62
views
graphtheory
graphcoloring
+3
votes
0
answers
2
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
asked
Jan 10
in
Graph Theory
by
Mk Utkarsh
Boss
(
7.1k
points)

68
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
+1
vote
0
answers
3
#GRAPH THEORY
asked
Dec 23, 2017
in
Graph Theory
by
Abhijeet_Kumar
Boss
(
7.2k
points)

80
views
graphtheory
discretemathematics
graphcoloring
+8
votes
1
answer
4
TIFR2018A9
How many ways are there to assign colours from range $\left\{1,2,...,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4}  4r^{3}$ $r^{4}5r^{3}+8r^{2}4r$ $r^{4}4r^{3}+9r^{2}3r$ $r^{4}5r^{3}+10r^{2}15r$
asked
Dec 10, 2017
in
Graph Theory
by
Rohit Gupta 8
Active
(
2.3k
points)

243
views
tifr2018
graphtheory
graphcoloring
+1
vote
2
answers
5
#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
asked
Nov 21, 2017
in
Graph Theory
by
Harish Karnam
Active
(
2k
points)

109
views
graphtheory
graphcoloring
0
votes
0
answers
6
GRAPH THEORY EDGE COLORING
asked
Nov 5, 2017
in
Algorithms
by
Parshu gate
Boss
(
6.4k
points)

74
views
graphtheory
graphcoloring
edgecoloring
+11
votes
2
answers
7
TIFR2017B10
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 ... 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
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

346
views
tifr2017
graphtheory
graphcoloring
+18
votes
3
answers
8
TIFR2017B1
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$
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

477
views
tifr2017
graphtheory
graphcoloring
0
votes
1
answer
9
Algocoloring
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?
asked
Dec 9, 2016
in
Algorithms
by
srestha
Veteran
(
81.5k
points)

106
views
graphcoloring
+2
votes
1
answer
10
UGCNETJune2012III31
The upper bound of computing time of m colouring decision problem is $O(nm)$ $O(n^m)$ $O(nm^n)$ $O(n^mm^n)$
asked
Jul 7, 2016
in
Programming
by
jothee
Veteran
(
108k
points)

194
views
ugcnetjune2012iii
graphs
graphcoloring
+1
vote
3
answers
11
UGCNETJune2012II4
The number of colours required to properly colour the vertices of every planer graph is 2 3 4 5
asked
Jul 4, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

789
views
ugcnetjune2012ii
graphtheory
graphcoloring
+4
votes
2
answers
12
ISRO200707
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is 1 k k1 k/2
asked
Jun 10, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

1.5k
views
isro2007
graphtheory
graphcoloring
chromaticnumber
+1
vote
4
answers
13
IISCCSAResearchTest10
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?
asked
Jun 8, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

186
views
iisccsaresearch2016
descriptive
graphtheory
graphcoloring
iiscinterview
+2
votes
0
answers
14
CMI2015A04b
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the ... courses with an overlapping audience. In this setting, the graph theoretic question to be answered is: Find a minimal colouring.
asked
May 29, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

122
views
cmi2015
descriptive
graphtheory
graphcoloring
+3
votes
1
answer
15
CMI2015A03
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 ... any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

81
views
cmi2015
graphtheory
graphcoloring
+1
vote
0
answers
16
CMI2011B01a
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. ... possible to colour each building with either red or blue so that every road connects a red and blue building?
asked
May 19, 2016
in
Graph Theory
by
jothee
Veteran
(
108k
points)

47
views
cmi2011
descriptive
graphcoloring
+17
votes
5
answers
17
GATE2016203
The minimum number of colours that is sufficient to vertexcolour any planar graph is ________.
asked
Feb 12, 2016
in
Graph Theory
by
Akash Kanase
Veteran
(
49.5k
points)

3.1k
views
gate20162
graphtheory
graphcoloring
normal
numericalanswers
+9
votes
2
answers
18
TIFR2013B1
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 ... n}{\chi \left(G\right)}$ $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above.
asked
Nov 5, 2015
in
Graph Theory
by
makhdoom ghaya
Veteran
(
47.8k
points)

456
views
tifr2013
graphtheory
graphcoloring
+3
votes
4
answers
19
graph coloring
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
asked
Jun 26, 2015
in
Graph Theory
by
Sankaranarayanan P.N
Veteran
(
12.1k
points)

939
views
graphtheory
graphcoloring
+26
votes
3
answers
20
GATE2006IT25
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)$
asked
Oct 31, 2014
in
Graph Theory
by
Ishrat Jahan
Veteran
(
22k
points)

1.6k
views
gate2006it
graphtheory
graphcoloring
normal
+17
votes
2
answers
21
GATE2008IT3
What is the chromatic number of the following graph? 2 3 4 5
asked
Oct 28, 2014
in
Graph Theory
by
Ishrat Jahan
Veteran
(
22k
points)

1.2k
views
gate2008it
graphtheory
graphcoloring
normal
+15
votes
5
answers
22
GATE200477
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
asked
Sep 19, 2014
in
Graph Theory
by
Kathleen
Veteran
(
69k
points)

1.3k
views
gate2004
graphtheory
graphcoloring
easy
+17
votes
2
answers
23
GATE20021.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$ $n2 \left \lfloor \frac{n}{2} \right \rfloor+2$
asked
Sep 16, 2014
in
Graph Theory
by
Kathleen
Veteran
(
69k
points)

1.5k
views
gate2002
graphtheory
graphcoloring
normal
+21
votes
5
answers
24
GATE20092
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 n1 n
asked
Sep 16, 2014
in
Graph Theory
by
gatecse
Veteran
(
18k
points)

2k
views
gate2009
graphtheory
graphcoloring
normal
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
Follow @csegate
Gatecse
Recent questions tagged graphcoloring
Recent Blog Comments
Okay Thanks
i think they call everyone ith a score higher ...
@raviyogi Do you know what was the cutoff ot IIT ...
I think the exam has not yet been created.
Then why it's not appearing as a separate exam in ...
33,707
questions
40,253
answers
114,361
comments
38,874
users