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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged graphcoloring
+1
vote
1
answer
1
CMI2019A7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

65
views
cmi2019
graphtheory
graphcoloring
spanningtree
vertexcover
descriptive
+2
votes
0
answers
2
GO2019FLT151
... Consider the above 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?
asked
Dec 27, 2018
in
Graph Theory
by
Ruturaj Mohanty
Active
(
2.7k
points)

190
views
go2019flt1
numericalanswers
graphcoloring
graphtheory
+2
votes
1
answer
3
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?
asked
Nov 27, 2018
in
Graph Theory
by
Balaji Jegan
Active
(
5k
points)

333
views
graphtheory
graphcoloring
permutationandcombination
+1
vote
1
answer
4
Zeal Test Series 2019: Graph Theory  Graph Coloring
what is index ?
asked
Nov 19, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
5.9k
points)

138
views
zeal
graphtheory
graphcoloring
zeal2019
0
votes
0
answers
5
Regular graph coloring
If G is a connected kregular graph with chromatic number k+1, then find the number of edges in G?
asked
Nov 6, 2018
in
Graph Theory
by
dan31
Junior
(
883
points)

235
views
graphtheory
graphcoloring
+1
vote
1
answer
6
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 _________.
asked
Sep 21, 2018
in
Graph Theory
by
srestha
Veteran
(
119k
points)

174
views
graphtheory
graphcoloring
0
votes
0
answers
7
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
asked
Jun 30, 2018
in
Graph Theory
by
ejaz
(
199
points)

56
views
graphcoloring
0
votes
2
answers
8
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, 2018
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
29.1k
points)

152
views
graphtheory
graphcoloring
0
votes
1
answer
9
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, 2018
in
Graph Theory
by
RahulRoy31
(
187
points)

93
views
graphtheory
graphcoloring
+18
votes
4
answers
10
GATE201818
The chromatic number of the following graph is _____
asked
Feb 14, 2018
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

2.9k
views
graphtheory
graphcoloring
numericalanswers
gate2018
+3
votes
1
answer
11
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, 2018
in
Graph Theory
by
Shubhanshu
Boss
(
18.3k
points)

273
views
graphtheory
graphcoloring
+5
votes
2
answers
12
MadeEasy Test Series 2018: Graph Theory  Graph Coloring
answer given is 4. Please provide a detailed solution.
asked
Jan 11, 2018
in
Graph Theory
by
kapilbk1996
(
409
points)

180
views
graphtheory
graphcoloring
madeeasytestseries
madeeasytestseries2018
+6
votes
0
answers
13
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, 2018
in
Graph Theory
by
Mk Utkarsh
Boss
(
36.5k
points)

265
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
0
votes
0
answers
14
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.3k
points)

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

117
views
graphtheory
discretemathematics
graphcoloring
+23
votes
3
answers
16
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
(
2k
points)

1k
views
tifr2018
graphtheory
graphcoloring
+1
vote
2
answers
17
#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.3k
points)

228
views
graphtheory
graphcoloring
+2
votes
0
answers
18
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
(
3.1k
points)

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

126
views
graphtheory
graphcoloring
edgecoloring
0
votes
0
answers
20
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
(
12.1k
points)

274
views
graphtheory
graphcoloring
+1
vote
0
answers
21
Graphs
We know that every 2colourable graph is bipartite. To prove that we divide the vertices having different colors and put them separately in 2 partitions. Suppose there are n vertices in an empty graph and they are randomly colored as 1 and 2. The ones with '1' are placed ... this be called a bipartite case even when there is no connection b/w the vertices of partition A and B? If not, why?
asked
Sep 30, 2017
in
Graph Theory
by
MiNiPanda
Boss
(
23.5k
points)

119
views
graphcoloring
+1
vote
0
answers
22
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?
asked
Sep 10, 2017
in
Algorithms
by
kunalv
(
85
points)

69
views
algorithms
graphcoloring
treecoloring
virtualgatetestseries
+1
vote
2
answers
23
#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.9k
points)

272
views
graphtheory
discretemathematics
graphcoloring
0
votes
4
answers
24
GateForum Test Series: Graph Theory  Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____
asked
Jan 9, 2017
in
Graph Theory
by
Jason GATE
Active
(
3.8k
points)

405
views
gateforumtestseries
engineeringmathematics
discretemathematics
graphtheory
graph
graphcoloring
+20
votes
2
answers
25
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$ ... of 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
(
105k
points)

692
views
tifr2017
graphtheory
graphcoloring
+31
votes
3
answers
26
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
(
105k
points)

1.1k
views
tifr2017
graphtheory
graphcoloring
+1
vote
1
answer
27
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
(
119k
points)

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

194
views
graphcoloring
discrete
engineeringmathematics
+1
vote
1
answer
29
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
(
33k
points)

523
views
algorithms
datastructures
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graphcoloring
Recent Blog Comments
Link for raising objection has been...
I have never been so happy to be proved wrong.....
In 2018 there are 25 post for general candidate(...
a youtuber named torq... has uploaded a video...
Ratio will more likely be 1:4,at least thats what...
50,737
questions
57,299
answers
198,279
comments
104,993
users