menu
search
Log In

GO Book for GATECSE 2022

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

Subjects


GATE Overflow
Recent questions tagged graph-coloring

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

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$
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$
asked Mar 30, 2020 in Graph Theory Lakshman Patel RJIT 1k 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
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
asked Mar 24, 2020 in Graph Theory jothee 249 views
0 votes
3 answers
3
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)$
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)$
asked Feb 11, 2020 in Graph Theory Lakshman Patel RJIT 526 views
2 votes
1 answer
4
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.
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 requires a ... to solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked Sep 13, 2019 in Graph Theory gatecse 251 views
4 votes
1 answer
6
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?
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 Balaji Jegan 813 views
0 votes
0 answers
8
Regular graph coloring
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
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 dan31 516 views
1 vote
1 answer
9
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 _________.
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 srestha 410 views
0 votes
0 answers
10
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
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 ejaz 151 views
1 vote
2 answers
11
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.
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 and b with colour 2 ... and how 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 Ayush Upadhyaya 341 views
0 votes
1 answer
12
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}$
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 RahulRoy31 146 views
22 votes
5 answers
13
GATE CSE 2018 | Question: 18
The chromatic number of the following graph is _____
The chromatic number of the following graph is _____
asked Feb 14, 2018 in Graph Theory gatecse 6.1k views
3 votes
1 answer
14
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?
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 _________. In the ... than 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 Shubhanshu 707 views
7 votes
0 answers
16
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
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 Mk Utkarsh 481 views
0 votes
0 answers
17
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
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 akb1115 126 views
1 vote
0 answers
18
#GRAPH THEORY
asked Dec 23, 2017 in Graph Theory Abhijeet_Kumar 231 views
25 votes
6 answers
19
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$
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 Rohit Gupta 8 2.5k views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...