Some properties of star-perfect graphs

Document Type : Original paper

Authors

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

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 July 2023

Files

Share

How to cite

Statistics