The Gateway to Computer Science Excellence
+2 votes
290 views
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 by Active (3.2k points) | 290 views
+5

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.

+4

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

 

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

Please log in or register to answer this question.

Related questions

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
50,833 questions
57,705 answers
199,411 comments
107,574 users