Recent questions tagged graph-coloring

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

go_editor asked in Graph Theory Mar 24, 2020

405 views

16 votes

5 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

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

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

417 views

5 votes

1 answer

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

594 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

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

768 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

754 views

2 votes

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

711 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

244 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

693 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

247 views

24 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

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

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

447 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

683 views

Page:

1
2
3
next »

Follow @gateoverflow

Recent questions tagged graph-coloring

Search GATE Overflow for GATE CSE