GATE CSE
First time here? Checkout the FAQ!
x
0 votes
81 views
Let G be a planar graph such that every face is bordered by exactly 3 edges.Which of the following can never be the value for χ(G) ? (where χ(G) is the chromatic number of G)

a)  2

b)  3

c)  4

d)  None of these

PS : (Explain: "every face is bordered by exactly 3 edges. ")
asked in Graph Theory by Loyal (3.2k points)  
edited by | 81 views

2 Answers

+1 vote

I think answer should be (A) because K2 require 2 colors and is not bounded by three edges but Krequire 3 colors, and K4 require 4 colors to color them and both of them are planar graphs and are bounded by exactly 3 edges. Moreover, every face is bordered by exactly three edges means that every REGION formed within the graph must have exactly three edges surrounding them. Have a look at the graphs, every region within graph K3 and K4 are bounded by exactly three edges but K2 is not.

answered by Active (1.5k points)  
edited by
0 votes
as it mentions it's planar and every face is bounded by exactly three edges so the only possibility we have K3 which has chromatic number X(G) =3
answered by Boss (5.1k points)  


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2606 Points

  5. Debashish Deka

    2088 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1312 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1166 Points

  10. Sanjay Sharma

    984 Points

Monthly Topper: Rs. 500 gift card

21,438 questions
26,753 answers
60,913 comments
22,926 users