in Graph Theory
858 views
2 votes
2 votes
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
in Graph Theory
858 views

3 Comments

Let G be a planar Graph Such that every phase is bordered by exactly 3 edges

since graph conain odd length cycle, its chromatic no. X(G)>=3

so 2 can never be X(G), hence option a is correct.

5
5

Yes option a) is correct 2 is not possible because when a region consist exactly 3 edges means vertices joining them are adjacent and should be colored uniquely. You can also observe this with example below

 

4
4
$\chi (G) \leq \Delta (G) + 1$
0
0

Please log in or register to answer this question.