GATE CSE 2018 | Question: 18

Question

The chromatic number of the following graph is _____

Comments

It simply can’t be 2. The chromatic number has to be 3

---

Planar graphs be coloured with at max 4 colours... I didnt even try to colour the graph before selecting that, samajh ke Ratta maaro, par always use logic before directly applying any tips/tricks... Valuable lesson.

---

Subgraph with odd length cycle has colours i.e. (χ) >= 3

Answer 1

Here, Independent sets, $S_1 = \{a,d\}, S_2 = \{b,e\}, S_3 = \{c,f\}$

Therefore, vertices of $S_1$ has no connection between each other [∵ $a$ & $d$ are not connected by an edge]

$ S_1 ⇒  $put ${\color{red}{RED}}$

Vertices of $S_2$ has no connection between each other [∵ $b$ & $e$ are not connected by an edge]

$ S_2 ⇒  $put ${\color{GREEN}{GREEN}}$

Vertices of $S_3$ has no connection between each other [∵ $c$ & $f$ are not connected by an edge]

$ S_3 ⇒  $put ${\color{BLUE}{BLUE}}$

∴ These graph has chromatic number as $3$.

Explanation: Why solving by independent sets?

Independent set means a set containing vertices & each & every vertex of this set is independent to each other i.e. if there are $3$ vertices in an independent set, then each vertex of this set does not connected to other vertex of this set by an edge.

Suppose, there are two independent sets $(S_1$ & $S_2)$. Then any vertex of $S_1$ has connection(share an edge) to any vertex of set $S_2$.

∵ $S_1,S_2, S_3$ are different independent sets & they share some connection between them, we put different colours to different sets.

$S_1$ share connections to $S_2$ & $S_3$

∴ Put  ${\color{RED}{RED}}$ to $S_1$, not $S_2$ & $S_3$

Similarly, $S_2$ share connections to $S_1$ & $S_3$

∴ Put  ${\color{GREEN}{GREEN}}$ to $S_2$, not $S_1$ & $S_3$

$S_3$ share connections to $S_1$ & $S_2$

∴ Put  ${\color{BLUE}{BLUE}}$ to $S_3$, not $S_1$ & $S_2$

The advantage of following this method is when we have a complicated graph then we do not need to continuously see whether any vertex is adjacent to each other when we colour any vertex.

Comments

@Ayush Upadhyaya Sir, your answer is of a great help in understanding Chromatic Partitioning. I feel this question must have a tag: “Chromatic partitioning” as it is difficult to find such an easy and clear explanation on this topic.

---

omg this is too depth thanks for that but can we say its chromatic number is 3 because it have odd length cycle?

---

@pavansan
We can't say Chromatic Number = 3
But we can say Chromatic Number >= 3

CounterExample - 

This Graph contain Odd Length Cycle but Chromatic Number is 4

Answer 2

$3$ is answer. 

Comments

nice!

Answer 3

Answer is 3

Answer 4

The correct answer is 3.
 

 

Answer 5

Ans is 3

Answer 6

the graph is planar therefore 
X <= 4 and also the graph has a triangle means K3(complete graph with 3 vertices)  therefore X >= 3 
comparing two results we can directly say X=3 

for a complete subgraph Km 
X >= m