1.

Berge graph is similar to ______ due to strong perfect graph theorem.(a) line graph(b) perfect graph(c) bar graph(d) triangle free graphThis question was addressed to me in an online interview.My question comes from Graphs Properties topic in portion Graphs of Discrete Mathematics

Answer» RIGHT answer is (b) perfect GRAPH

For EXPLANATION I would say: In a perfect graph, the chromatic number of each and every induced subgraph is equal to the size of the largest CLIQUE of that subgraph. These perfect graphs are same as Berge graphs due to strong perfect graph THEOREM.


Discussion

No Comment Found

Related InterviewSolutions