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. For hardcopy of previous year questions please see
here
Recent questions tagged graphcoloring
0
votes
2
answers
1
SelfDoubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate201818?show=204092#q204092 My doubt is Suppose, I try to colour the vertices of this graph as follows First I colour vertex a and f with colour 1. Then I colour vertex e ... what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours.
asked
Jun 7
in
Graph Theory
by
Ayush Upadhyaya
Loyal
(
9k
points)

66
views
graphtheory
graphcoloring
0
votes
1
answer
2
GraphTheory_Problem_testpaper
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bits of strings of length $n$. We have an edge between vertex $u$ and $v$ if and only if $u$ and $v$ differ exactly in one bit position. The ratio of chromatic number of $G$ to the diameter of $G$ is . $\dfrac{1}{(2^{n1})}$ $\dfrac{1}{n}$ $\dfrac{2}{n}$ $\dfrac{3}{n}$
asked
Mar 16
in
Graph Theory
by
RahulRoy31
(
199
points)

69
views
graphtheory
graphcoloring
+7
votes
4
answers
3
GATE201818
The chromatic number of the following graph is _____
asked
Feb 14
in
Graph Theory
by
gatecse
Boss
(
18k
points)

1.4k
views
graphtheory
graphcoloring
numericalanswers
gate2018
+3
votes
1
answer
4
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 _________. ... Red and 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
Boss
(
15k
points)

105
views
graphtheory
graphcoloring
+3
votes
0
answers
5
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
(
12.6k
points)

103
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
0
votes
0
answers
6
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
asked
Dec 24, 2017
in
Graph Theory
by
akb1115
Active
(
3.1k
points)

44
views
graphtheory
graphcoloring
+1
vote
0
answers
7
#GRAPH THEORY
asked
Dec 23, 2017
in
Graph Theory
by
Abhijeet_Kumar
Junior
(
785
points)

94
views
graphtheory
discretemathematics
graphcoloring
+8
votes
2
answers
8
TIFR2018A9
How many ways are there to assign colours from range $\left\{1,2,\ldots,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.1k
points)

321
views
tifr2018
graphtheory
graphcoloring
+1
vote
2
answers
9
#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
(
1.2k
points)

124
views
graphtheory
graphcoloring
+1
vote
0
answers
10
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
asked
Nov 11, 2017
in
Graph Theory
by
Parshu gate
Active
(
4.9k
points)

159
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
graphcoloring
0
votes
0
answers
11
GRAPH THEORY EDGE COLORING
asked
Nov 5, 2017
in
Algorithms
by
Parshu gate
Active
(
4.9k
points)

92
views
graphtheory
graphcoloring
edgecoloring
0
votes
0
answers
12
Chromatic polynomials
Check which of the following can be chromatic polynomials of a nonnull graph ? i) x5  4x3  2x2 + x + 4 ii) x6  3x5 + 2x4  1 P.S I know for a nonnull graph G, X(G) (i.e. chromatic number) is at least 2. How to proceed further ??
asked
Oct 24, 2017
in
Mathematical Logic
by
just_bhavana
Boss
(
11.9k
points)

73
views
graphtheory
graphcoloring
0
votes
2
answers
13
#Chromatic number , Planarity
Let G be a planar graph such that every face is bordered by exactly 3 edges.Which of the following can never be the value for χ(G) ? (where χ(G) is the chromatic number of G) a) 2 b) 3 c) 4 d) None of these PS : (Explain: "every face is bordered by exactly 3 edges. ")
asked
Jan 11, 2017
in
Graph Theory
by
smartmeet
Active
(
4.8k
points)

141
views
graphtheory
discretemathematics
graphcoloring
0
votes
3
answers
14
Test series
The Chromatic Number of Cycle Graph with 7 vertices _____
asked
Jan 9, 2017
in
Graph Theory
by
Jason GATE
Active
(
3.6k
points)

221
views
gateforumtestseries
graphtheory
graphcoloring
+12
votes
2
answers
15
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 degree at most $d$ then ... 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
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

376
views
tifr2017
graphtheory
graphcoloring
+20
votes
3
answers
16
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
(
98.5k
points)

535
views
tifr2017
graphtheory
graphcoloring
0
votes
1
answer
17
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
(
86.9k
points)

112
views
graphcoloring
+2
votes
2
answers
18
Made easy
What is the chromatic number of following graphs? 1) 2)
asked
Aug 10, 2016
in
Graph Theory
by
gaurav9822
(
263
points)

113
views
graphcoloring
discrete
engineeringmathematics
+1
vote
1
answer
19
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?
asked
Jul 12, 2016
in
Programming
by
sh!va
Boss
(
34.1k
points)

270
views
algorithms
datastructure
graphcoloring
0
votes
1
answer
20
chromatic number
asked
Jul 7, 2016
in
Graph Theory
by
Imarati Gupta
Junior
(
519
points)

324
views
graphtheory
graphcoloring
+3
votes
1
answer
21
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
(
98.5k
points)

278
views
ugcnetjune2012iii
graphs
graphcoloring
+1
vote
3
answers
22
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
(
98.5k
points)

1.1k
views
ugcnetjune2012ii
graphtheory
graphcoloring
+5
votes
2
answers
23
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
(
98.5k
points)

2k
views
isro2007
graphtheory
graphcoloring
+1
vote
4
answers
24
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
(
98.5k
points)

211
views
iisccsaresearch2016
descriptive
graphtheory
graphcoloring
iiscinterview
+2
votes
0
answers
25
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 administration now knows ... of 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
(
98.5k
points)

143
views
cmi2015
descriptive
graphtheory
graphcoloring
+3
votes
1
answer
26
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 blue coloured edge ... endpoint of 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
(
98.5k
points)

95
views
cmi2015
graphtheory
graphcoloring
+1
vote
1
answer
27
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. 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?
asked
May 19, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

62
views
cmi2011
descriptive
graphcoloring
+18
votes
5
answers
28
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
Boss
(
42.5k
points)

3.5k
views
gate20162
graphtheory
graphcoloring
normal
numericalanswers
+13
votes
1
answer
29
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/gate2006it_25
asked
Jan 28, 2016
in
Graph Theory
by
pC
Boss
(
22k
points)

720
views
engineeringmathematics
algorithms
hamingdistance
graphcoloring
Page:
1
2
next »
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
IISc CSA and CDCS written test and interview Experince
IIIT Hyderabad Interview Experience
My failure, Oh wait SUCCESS journey
ALGORITHMS CHECKLIST:
A Failure who got into IISc
Follow @csegate
Gatecse
Recent questions tagged graphcoloring
Recent Blog Comments
Sir I didn't get an email for GO classroom, ...
any one with marks less than 125 selected?
Thank you @Arjun Sir, @NamitaAIR1, @Priyanka, ...
Your story is very inspiring for the boys like me ...
So you completed your Btech in 5 yrs? How could ...
36,194
questions
43,647
answers
124,091
comments
42,931
users