Planarity and Choosability of p-petal graphs
by
Kolappan Velayutham
No. 6, 18th street, P-Block, Anna Nagar, Chennai, Tamil Nadu, India. Pin code 600 040.
Coauthors: Dr. M. Murugan, Reader and Head, Tamil Nadu Open University, Chennai, Tamil Nadu, India.

A Petal graph has vertices of degree either two or three. The subgraph induced by the vertices of degree three is a cycle such that each edge of the graph is adjacent to atleast one vertex of this cycle. In this paper, a specific type of petal graphs named p-petal graph, is introduced and the planarity of this graph is studied. The necessary and sufficient condition for a p-petal graph to be planar is given. Thomassen proved that every planar graph of girth atleast 5 is 3-choosable. Using this result, it is proved that every planar p-petal graph is 3-choosable.

Key words: Petal graph, Planarity, Choosability.

Date received: March 22, 2008