[Solved] Which of the following is not a property of perfect graph?

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
Which of the following is not a property...

Q.	Which of the following is not a property of perfect graph?
A.	compliment of line graph of bipartite graph
B.	compliment of bipartite graph
C.	line graph of bipartite graph
D.	line graph
Answer» D. line graph
Explanation: tthe compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is known as a perfect graph in graph theory. normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

Every Perfect graph has forbidden graph characterization.
A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
Which complete graph is not present in minor of Outer Planar Graph?
Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
Which of the following is not a property of the bipartite graph?
Which graph is used to define the claw free graph?
Which graph cannot contain K3, 3 as a minor of graph?
Consider a complete graph G with 4 vertices. The graph G has spanning trees.
If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.