# Recent questions tagged graph-coloring 1 vote
4 answers
1
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$
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
9 votes
3 answers
3
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 _______
0 votes
3 answers
4
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)$
2 votes
2 answers
5
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.
5 votes
0 answers
6
... $7$ nodes (namely A , B, C, D, E, F, G). The Chromatic number of the given graph is?
4 votes
1 answer
7
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?
3 votes
1 answer
8
what is index ?
0 votes
0 answers
9
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?
1 vote
1 answer
10
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 _________.
0 votes
0 answers
11
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
1 vote
2 answers
12
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.
0 votes
1 answer
13
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}$
23 votes
5 answers
14
The chromatic number of the following graph is _____
3 votes
1 answer
15
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?
7 votes
2 answers
16
answer given is 4. Please provide a detailed solution.
8 votes
0 answers
17
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
0 votes
0 answers
18
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
1 vote
0 answers
19