The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
254 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.1k points) | 254 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

 

Please log in or register to answer this question.

Related questions

0 votes
1 answer
5
asked Jul 7, 2016 in Graph Theory by Imarati Gupta (339 points) | 438 views
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,339 questions
55,765 answers
192,355 comments
90,815 users