Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged graph-coloring
1
vote
2
answers
61
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?
go_editor
asked
in
Graph Theory
May 19, 2016
by
go_editor
424
views
cmi2011
descriptive
graph-coloring
39
votes
5
answers
62
GATE CSE 2016 Set 2 | Question: 03
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
Akash Kanase
asked
in
Graph Theory
Feb 12, 2016
by
Akash Kanase
11.8k
views
gatecse-2016-set2
graph-theory
graph-coloring
normal
numerical-answers
16
votes
1
answer
63
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
pC
asked
in
Graph Theory
Jan 28, 2016
by
pC
1.9k
views
engineering-mathematics
algorithms
graph-coloring
24
votes
4
answers
64
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
makhdoom ghaya
asked
in
Graph Theory
Nov 5, 2015
by
makhdoom ghaya
3.2k
views
tifr2013
graph-theory
graph-coloring
4
votes
4
answers
65
graph coloring
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
Sankaranarayanan P.N
asked
in
Graph Theory
Jun 26, 2015
by
Sankaranarayanan P.N
2.3k
views
graph-theory
graph-coloring
58
votes
7
answers
66
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)$
Ishrat Jahan
asked
in
Graph Theory
Oct 31, 2014
by
Ishrat Jahan
9.9k
views
gateit-2006
graph-theory
graph-coloring
normal
33
votes
4
answers
67
GATE IT 2008 | Question: 3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
Ishrat Jahan
asked
in
Graph Theory
Oct 28, 2014
by
Ishrat Jahan
6.5k
views
gateit-2008
graph-theory
graph-coloring
normal
33
votes
5
answers
68
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$
Kathleen
asked
in
Graph Theory
Sep 19, 2014
by
Kathleen
9.9k
views
gatecse-2004
graph-theory
graph-coloring
easy
39
votes
4
answers
69
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$
Kathleen
asked
in
Graph Theory
Sep 15, 2014
by
Kathleen
8.5k
views
gatecse-2002
graph-theory
graph-coloring
normal
45
votes
10
answers
70
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$
gatecse
asked
in
Graph Theory
Sep 15, 2014
by
gatecse
10.0k
views
gatecse-2009
graph-theory
graph-coloring
normal
Page:
« prev
1
2
3
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged graph-coloring
Recent Blog Comments
Maximum age limit changed from 35 yrs. to 28...
Hmm, sir totally getting your point ☺️☺️....
yes, that's fine. But saying so in a public forum...
@gatecse Sir , I know you are correct. I just...
@Deepanshu I have to disagree there...