search
Log In

Recent questions tagged graph-coloring

1 vote
4 answers
1
0 votes
1 answer
2
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 219 views
0 votes
3 answers
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 392 views
2 votes
1 answer
4
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 225 views
4 votes
1 answer
6
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 750 views
0 votes
0 answers
8
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 478 views
1 vote
1 answer
9
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 379 views
0 votes
0 answers
10
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 140 views
1 vote
2 answers
11
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 325 views
0 votes
1 answer
12
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 136 views
21 votes
5 answers
13
The chromatic number of the following graph is _____
asked Feb 14, 2018 in Graph Theory gatecse 5.4k views
3 votes
1 answer
14
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 626 views
7 votes
0 answers
16
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 461 views
0 votes
0 answers
17
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 120 views
1 vote
0 answers
18
24 votes
6 answers
19
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.2k views
1 vote
2 answers
20
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 Harish Karnam 327 views
...