Recent questions tagged graph-coloring

0 votes

2 answers

1

Self-Doubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate2018-18?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 (8.7k points) | 63 views

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^{n-1})}$ $\dfrac{1}{n}$ $\dfrac{2}{n}$ $\dfrac{3}{n}$

asked Mar 16 in Graph Theory by RahulRoy31 (199 points) | 66 views

+7 votes

4 answers

3

GATE2018-18
The chromatic number of the following graph is _____

asked Feb 14 in Graph Theory by gatecse Boss (18k points) | 1.4k views

+3 votes

0 answers

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) | 98 views

+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) | 100 views

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

+1 vote

0 answers

7

#GRAPH THEORY

asked Dec 23, 2017 in Graph Theory by Abhijeet_Kumar Junior (785 points) | 92 views

+8 votes

2 answers

8

TIFR2018-A-9
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) | 319 views

+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

+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) | 157 views

0 votes

0 answers

11

GRAPH THEORY EDGE COLORING

asked Nov 5, 2017 in Algorithms by Parshu gate Active (4.9k points) | 92 views

0 votes

0 answers

12

Chromatic polynomials
Check which of the following can be chromatic polynomials of a non-null graph ? i) x5 - 4x3 - 2x2 + x + 4 ii) x6 - 3x5 + 2x4 - 1 P.S I know for a non-null 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

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

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

+12 votes

2 answers

15

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 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) | 374 views

+20 votes

3 answers

16

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 (98.5k points) | 533 views

0 votes

1 answer

17

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 (86.4k points) | 112 views

+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) | 109 views

+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 (34k points) | 267 views

0 votes

1 answer

20

chromatic number

asked Jul 7, 2016 in Graph Theory by Imarati Gupta Junior (519 points) | 320 views

+3 votes

1 answer

21

UGCNET-June2012-III-31
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) | 268 views

+1 vote

3 answers

22

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 (98.5k points) | 1.1k views

+5 votes

2 answers

23

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 (98.5k points) | 2k views

+1 vote

4 answers

24

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 (98.5k points) | 211 views

+2 votes

0 answers

25

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

+3 votes

1 answer

26

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 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) | 93 views

+1 vote

1 answer

27

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?

asked May 19, 2016 in Graph Theory by jothee Veteran (98.5k points) | 62 views

+18 votes

5 answers

28

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 Boss (42.5k points) | 3.5k views

+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/gate2006-it_25

asked Jan 28, 2016 in Graph Theory by pC Boss (22k points) | 718 views

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 questions tagged graph-coloring

Recent Posts

Recent Blog Comments