Recent questions tagged graph-coloring

1 vote

4 answers

1

NIELIT 2017 DEC Scientist B - Section B: 52
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$

Lakshman Patel RJIT asked in Graph Theory Mar 30, 2020

by Lakshman Patel RJIT

1.3k views

0 votes

1 answer

2

UGCNET-Jan2017-II: 5
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above

jothee asked in Graph Theory Mar 24, 2020

by jothee

324 views

12 votes

4 answers

3

GATE CSE 2020 | Question: 52
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Arjun asked in Graph Theory Feb 12, 2020

by Arjun

5.4k views

0 votes

3 answers

4

TIFR2020-B-11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$

Lakshman Patel RJIT asked in Graph Theory Feb 11, 2020

by Lakshman Patel RJIT

851 views

3 votes

2 answers

5

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.

gatecse asked in Graph Theory Sep 13, 2019

310 views

5 votes

0 answers

6

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?

Ruturaj Mohanty asked in Graph Theory Dec 27, 2018

by Ruturaj Mohanty

416 views

4 votes

1 answer

7

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?

Balaji Jegan asked in Graph Theory Nov 27, 2018

by Balaji Jegan

964 views

3 votes

1 answer

8

Zeal Test Series 2019: Graph Theory - Graph Coloring
what is index ?

Prince Sindhiya asked in Graph Theory Nov 19, 2018

by Prince Sindhiya

617 views

0 votes

0 answers

9

Regular graph coloring
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?

dan31 asked in Graph Theory Nov 6, 2018

by dan31

594 views

1 vote

1 answer

10

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

srestha asked in Graph Theory Sep 21, 2018

517 views

0 votes

0 answers

11

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

ejaz asked in Graph Theory Jun 30, 2018

by ejaz

184 views

1 vote

2 answers

12

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.

Ayush Upadhyaya asked in Graph Theory Jun 7, 2018

by Ayush Upadhyaya

396 views

0 votes

1 answer

13

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

RahulRoy31 asked in Graph Theory Mar 16, 2018

171 views

23 votes

5 answers

14

GATE CSE 2018 | Question: 18
The chromatic number of the following graph is _____

gatecse asked in Graph Theory Feb 14, 2018

7.1k views

3 votes

1 answer

15

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?

Shubhanshu asked in Graph Theory Jan 22, 2018

893 views

7 votes

2 answers

16

MadeEasy Test Series 2018: Graph Theory - Graph Coloring
Consider the following graph: Which of the following will represents the chromatic number of the graph? answer given is 4. Please provide a detailed solution.

kapilbk1996 asked in Graph Theory Jan 11, 2018

341 views

8 votes

0 answers

17

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

Mk Utkarsh asked in Graph Theory Jan 10, 2018

546 views

0 votes

0 answers

18

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

akb1115 asked in Graph Theory Dec 24, 2017

159 views

1 vote

0 answers

19

Abhijeet_Kumar asked in Graph Theory Dec 23, 2017

by Abhijeet_Kumar

249 views

Page:

1
2
3
next »

Follow @gateoverflow

GATE Overflow

Recent questions tagged graph-coloring

Search GATE Overflow