Some properties of star-perfect graphs

Document Type : Original paper


Department of Mathematics, CHRIST(Deemed to be University), Bengaluru, India


For a finite simple graph $G=(V, E)$, $\theta_s(G)$ denotes the minimum number of induced stars contained in $G$ such that the union of their vertex sets is $V(G)$, and $ \alpha_s(G)$ denotes the maximum number of vertices in $G$ such that no two are contained in the same induced star of $G$. We call the graph $G$ star-perfect if $\alpha_s(H)=\theta_s(H)$, for every induced subgraph $H$ of $G$. We prove here that no cycle in a star-perfect graph has crossing chords and star-perfect graphs are planar. Also we present a few properties of star perfect graphs.


Main Subjects

[1] C. Berge, Les problémes de coloration en théorie des graphes, Publ. Inst. Statist. Univ. Paris 9 (1960), no. 2, 123–160.
[2] G. Chen, A. Gyárfás, and R.H. Schelp, Vertex colorings with a distance restriction, Discrete Math. 191 (1998), no. 1-3, 65–82.
[3] T.R. Jensen and B. Toft, Graph Coloring Problems, New York, NY, United States: John Wiley & Sons, 1995.
[4] L. Lovász, A characterization of perfect graphs, J. Combin. Theory, Ser. B 13 (1972), no. 2, 95–98.
[5] L. Lovász, Normal hypergraphs and perfect graph conjecture, Discrete Math. 2 (1972), no. 3, 253–267.
[6] S.B. Rao and G. Ravindra, A characterization of perfect total graphs, J. Math. Physical Sci. 11 (1977), no. 1, 25–26.
[7] G. Ravindra, S. Ghosh, and V. M. Abraham, Some results on star-perfect graphs, (submitted).
[8] G. Ravindra, S. Ghosh, J.V. Kureethara, and V.M. Abraham, A characterisation of star-perfect graphs, submitted.
[9] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, USA, 2001.