Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged graph-coloring
1
vote
2
answers
31
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
853
views
graph-theory
graph-coloring
28
votes
5
answers
32
GATE CSE 2018 | Question: 18
The chromatic number of the following graph is _____
gatecse
asked
in
Graph Theory
Feb 14, 2018
by
gatecse
9.1k
views
graph-theory
graph-coloring
numerical-answers
gatecse-2018
3
votes
1
answer
33
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
by
Shubhanshu
1.4k
views
graph-theory
graph-coloring
7
votes
2
answers
34
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
by
kapilbk1996
522
views
graph-theory
graph-coloring
made-easy-test-series
madeeasy-testseries-2018
8
votes
0
answers
35
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
by
Mk Utkarsh
736
views
graph-theory
discrete-mathematics
graph-connectivity
graph-coloring
0
votes
0
answers
36
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
by
akb1115
222
views
graph-theory
graph-coloring
1
vote
0
answers
37
#GRAPH THEORY
Abhijeet_Kumar
asked
in
Graph Theory
Dec 23, 2017
by
Abhijeet_Kumar
340
views
graph-theory
discrete-mathematics
graph-coloring
28
votes
6
answers
38
TIFR CSE 2018 | Part A | Question: 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$
Rohit Gupta 8
asked
in
Graph Theory
Dec 10, 2017
by
Rohit Gupta 8
3.6k
views
tifr2018
graph-theory
graph-coloring
1
vote
2
answers
39
#Graph theory #coloring
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
Harish Karnam
asked
in
Graph Theory
Nov 21, 2017
by
Harish Karnam
424
views
graph-theory
graph-coloring
2
votes
0
answers
40
chromatic number
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
Parshu gate
asked
in
Graph Theory
Nov 11, 2017
by
Parshu gate
858
views
graph-theory
discrete-mathematics
graph-connectivity
graph-matching
graph-coloring
0
votes
0
answers
41
GRAPH THEORY EDGE COLORING
Parshu gate
asked
in
Algorithms
Nov 5, 2017
by
Parshu gate
446
views
graph-theory
graph-coloring
edge-coloring
0
votes
0
answers
42
Chromatic polynomials
Check which of the following can be chromatic polynomials of a non-null graph ? i) x5 - 4x3 - 2x2 + x + 4 ii) x6 - 3x5 + 2x4 - 1 P.S I know for a non-null graph G, X(G) (i.e. chromatic number) is at least 2. How to proceed further ??
just_bhavana
asked
in
Mathematical Logic
Oct 24, 2017
by
just_bhavana
869
views
graph-theory
graph-coloring
1
vote
0
answers
43
Graphs
We know that every 2-colourable graph is bipartite. To prove that we divide the vertices having different colors and put them separately in 2 partitions. Suppose there are n vertices in an empty graph and they are randomly colored as 1 and 2. The ones with '1' are placed ... this be called a bipartite case even when there is no connection b/w the vertices of partition A and B? If not, why?
MiNiPanda
asked
in
Graph Theory
Sep 30, 2017
by
MiNiPanda
380
views
graph-coloring
1
vote
0
answers
44
Virtual Gate Test Series: Algorithms - Tree Coloring
Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent nodes get the same color?
kunalv
asked
in
Algorithms
Sep 10, 2017
by
kunalv
209
views
algorithms
graph-coloring
tree-coloring
virtual-gate-test-series
1
vote
2
answers
45
#Chromatic number , Planarity
Let G be a planar graph such that every face is bordered by exactly 3 edges.Which of the following can never be the value for χ(G) ? (where χ(G) is the chromatic number of G) a) 2 b) 3 c) 4 d) None of these PS : (Explain: "every face is bordered by exactly 3 edges. ")
smartmeet
asked
in
Graph Theory
Jan 11, 2017
by
smartmeet
905
views
graph-theory
discrete-mathematics
graph-coloring
0
votes
4
answers
46
GateForum Test Series: Graph Theory - Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____
Jason GATE
asked
in
Graph Theory
Jan 9, 2017
by
Jason GATE
1.7k
views
gateforum-test-series
engineering-mathematics
discrete-mathematics
graph-theory
graph-coloring
3
votes
4
answers
47
TIFR CSE 2016 | Part B | Question: 13
An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the following ... degree in $G$ There is a polynomial time algorithm to check if $G$ is $2$-colourable If $G$ has no triangle then it is $3$-colourable
go_editor
asked
in
Graph Theory
Dec 29, 2016
by
go_editor
530
views
tifr2016
graph-theory
graph-coloring
23
votes
2
answers
48
TIFR CSE 2017 | Part B | Question: 10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
2.1k
views
tifr2017
graph-theory
graph-coloring
34
votes
4
answers
49
TIFR CSE 2017 | Part B | Question: 1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
3.0k
views
tifr2017
graph-theory
graph-coloring
1
vote
1
answer
50
Algo-coloring
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent node gets same color?
srestha
asked
in
Graph Theory
Dec 9, 2016
by
srestha
466
views
graph-theory
graph-coloring
numerical-answers
1
vote
2
answers
51
GATE Overflow | Data Structures | Test 1 | Question: 19
What is the chromatic number of the following graph?
Arjun
asked
in
DS
Oct 10, 2016
by
Arjun
185
views
go-ds-1
data-structures
graph-theory
graph-coloring
numerical-answers
0
votes
3
answers
52
UGC NET CSE | June 2010 | Part 2 | Question: 4
$S_{1}$ : I teach algorithms and maths. $S_{2}$ : My professor teaches maths, electronics and computer science. $S_{3}$ : I have a student of maths. $S_{4}$ : Algorithm is a part of computer science. $S_{5}$ : Maths students know computer ... amongst the entities/actors as expressed in the sentences $S_{1}$ to $S_{5}$ above ? $2$ $3$ $4$ None of these
makhdoom ghaya
asked
in
Graph Theory
Sep 15, 2016
by
makhdoom ghaya
725
views
ugcnetcse-june2010-paper2
graph-coloring
2
votes
3
answers
53
Made easy
What is the chromatic number of following graphs? 1) 2)
gaurav9822
asked
in
Graph Theory
Aug 10, 2016
by
gaurav9822
590
views
graph-coloring
discrete
engineering-mathematics
1
vote
1
answer
54
Calculate chromatic number
Shiva draws a tree of N nodes, where a node can be adjacent to maximum of 4 other nodes. What is the minimum number of colors Shiva should use so that no two adjacent nodes get the same color? A. 5 B. 4 C. 3 D. 2 // Please explain how to solve this?
sh!va
asked
in
Programming
Jul 12, 2016
by
sh!va
3.3k
views
algorithms
data-structures
graph-coloring
0
votes
1
answer
55
chromatic number
Imarati Gupta
asked
in
Graph Theory
Jul 7, 2016
by
Imarati Gupta
787
views
graph-theory
graph-coloring
3
votes
2
answers
56
UGC NET CSE | June 2012 | Part 3 | Question: 31
The upper bound of computing time of m colouring decision problem is $O(nm)$ $O(n^m)$ $O(nm^n)$ $O(n^mm^n)$
go_editor
asked
in
Programming
Jul 7, 2016
by
go_editor
828
views
ugcnetcse-june2012-paper3
graph-theory
graph-coloring
1
vote
2
answers
57
UGC NET CSE | June 2012 | Part 2 | Question: 4
The number of colours required to properly colour the vertices of every planer graph is 2 3 4 5
go_editor
asked
in
Graph Theory
Jul 4, 2016
by
go_editor
8.3k
views
ugcnetcse-june2012-paper2
graph-theory
graph-coloring
6
votes
2
answers
58
ISRO2007-07
If a graph requires $k$ different colours for its proper colouring, then the chromatic number of the graph is 1 k k-1 k/2
go_editor
asked
in
Graph Theory
Jun 10, 2016
by
go_editor
3.4k
views
isro2007
graph-theory
graph-coloring
1
vote
4
answers
59
IISC-CSA-Research-Test-10
A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum number of colours required for proper vertex colouring of $G$ is called the chromatic number of $G$. Then what is the chromatic number of the cycle graph on 149 vertices?
go_editor
asked
in
Graph Theory
Jun 8, 2016
by
go_editor
499
views
iisccsaresearch2016
descriptive
graph-theory
graph-coloring
iisc-interview
3
votes
2
answers
60
CMI2015-A-03
Suppose each edge of an undirected graph is coloured using one of three colours - red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not ... endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. (A) and (C).
go_editor
asked
in
Graph Theory
May 27, 2016
by
go_editor
412
views
cmi2015
graph-theory
graph-coloring
Page:
« prev
1
2
3
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Recent Posts
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged graph-coloring
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...