#### IMSc Webinar

#### Determining perfectness of maximal planar graph in quadratic time.

#### Sameera Salam

##### IMSc

*Webinar: join at
https://zoom.us/j/95566670601?pwd=cmEvV1REeXk4UFFnWTAwK0xIaVhQZz09
We present a simple structural local characterization for perfect maximal planar graphs which helps to design an improved quadratic time for its recognition. A maximal planar graph is a drawing of a planar graph such that every face is a triangle. A graph is perfect if for each of its induced subgraphs, the chromatic number and the clique numbers are the same. It is known that a planar graph G is perfect if and only if it is odd hole-free. We show that a maximal planar graph G is not perfect if and only if it has a vertex subset X that is a vertex or end points of an edge or a triangle, and the vertices on the exterior face of the local neighbourhood of which, induces an odd hole.*

Done