Log In
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
0 votes
If a graph requires k different colors for its proper coloring,  then chromatic number of the graph is

(a) 1

(b) k

(c) k-1

(d) k/2
in Others 85 views

1 Answer

3 votes
The definition of chromatic number is minimum number of different colors required to color a graph

hence chromatic number is k only

Related questions

0 votes
1 answer
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
asked Jun 2, 2019 in Algorithms srestha 224 views
2 votes
2 answers
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
asked May 23, 2019 in Graph Theory srestha 357 views
1 vote
2 answers
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
asked May 19, 2019 in Graph Theory Hirak 430 views
1 vote
1 answer
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?
asked Apr 28, 2019 in Graph Theory gmrishikumar 245 views