Recent questions tagged graph-coloring - GATE Overflow

GATE CSE

For all GATE CSE Questions

First time here? Checkout the FAQ!

x

+4 votes

2 answers

1

TIFR2017-B-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 ... 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 (92.7k points) | 177 views

+10 votes

2 answers

2

TIFR2017-B-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$

asked Dec 23, 2016 in Graph Theory by jothee Veteran (92.7k points) | 259 views

0 votes

1 answer

3

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?

asked Dec 9, 2016 in Algorithms by srestha Veteran (65.2k points) | 84 views

+1 vote

3 answers

4

UGCNET-June2012-II-4
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 (92.7k points) | 612 views

+4 votes

2 answers

5

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

asked Jun 10, 2016 in Graph Theory by jothee Veteran (92.7k points) | 1k views

+1 vote

4 answers

6

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?

asked Jun 8, 2016 in Graph Theory by jothee Veteran (92.7k points) | 147 views

+2 votes

0 answers

7

CMI2015-A-04b
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 (92.7k points) | 90 views

+2 votes

1 answer

8

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 ... 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 (92.7k points) | 66 views

+1 vote

0 answers

9

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. ... 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 (92.7k points) | 41 views

+9 votes

5 answers

10

GATE2016-2-03
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

asked Feb 12, 2016 in Graph Theory by Akash Kanase Veteran (45.8k points) | 2k views

+6 votes

2 answers

11

TIFR2013-B-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 numbers of colours ... \chi (G)\leq a(G)$ $a(G)\geq n/\chi (G)$ $a(G)\leq n/\chi (G)$ None of the above.

asked Nov 5, 2015 in Graph Theory by makhdoom ghaya Veteran (39.8k points) | 266 views

+3 votes

4 answers

12

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 (11.6k points) | 669 views

+13 votes

3 answers

13

GATE2006-IT-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 ... bit). The ratio of the chromatic number of $G$ to the diameter of $G$ is 1/(2n-1) 1/n 2/n 3/n

asked Oct 31, 2014 in Graph Theory by Ishrat Jahan Veteran (21.3k points) | 998 views

+7 votes

2 answers

14

GATE2008-IT-3
What is the chromatic number of the following graph? 2 3 4 5

asked Oct 28, 2014 in Graph Theory by Ishrat Jahan Veteran (21.3k points) | 785 views

+8 votes

4 answers

15

GATE2004-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

asked Sep 19, 2014 in Graph Theory by Kathleen Veteran (66.3k points) | 837 views

+8 votes

2 answers

16

GATE2002-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$

asked Sep 15, 2014 in Graph Theory by Kathleen Veteran (66.3k points) | 1.1k views

+10 votes

5 answers

17

GATE2009-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

asked Sep 15, 2014 in Graph Theory by gatecse Veteran (13.5k points) | 1.1k views

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

Follow @csegate

Gatecse

Recent questions tagged graph-coloring

27,407 questions

35,256 answers

84,506 comments

33,480 users