Recent questions tagged graph-coloring

+1 vote

1 answer

1

CMI2019-A-7
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 in Others by gatecse Boss (16.8k points) | 33 views

+1 vote

0 answers

2

GO2019-FLT1-51
... 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 Others by Ruturaj Mohanty Active (2.6k points) | 169 views

+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 (4.9k points) | 314 views

+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.7k points) | 127 views

0 votes

0 answers

5

Regular graph coloring
If G is a connected k-regular 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) | 218 views

+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 (117k points) | 155 views

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

0 votes

2 answers

8

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, 2018 in Graph Theory by Ayush Upadhyaya Boss (27.7k points) | 148 views

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

asked Mar 16, 2018 in Graph Theory by RahulRoy31 (187 points) | 92 views

+16 votes

4 answers

10

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

asked Feb 14, 2018 in Graph Theory by gatecse Boss (16.8k points) | 2.6k views

+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.2k points) | 257 views

+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 (403 points) | 168 views

+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 (35.7k points) | 249 views

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

+1 vote

0 answers

15

#GRAPH THEORY

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

+21 votes

2 answers

16

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

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

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

0 votes

0 answers

19

GRAPH THEORY EDGE COLORING

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

0 votes

0 answers

20

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 (12.1k points) | 247 views

+1 vote

0 answers

21

Graphs
We know that every 2-colourable 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 (23k points) | 111 views

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

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

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.7k points) | 383 views

+19 votes

2 answers

25

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$ ... 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) | 650 views

+29 votes

3 answers

26

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 (105k points) | 1k views

+1 vote

1 answer

27

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 (117k points) | 144 views

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

+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 (32.5k points) | 500 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