Some properties of star-perfect graphs

Document Type : Short notes

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. https://doi.org/10.1016/S0012-365X(98)00094-6
[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. https://doi.org/10.1016/0095-8956(72)90045-7
[5] L. Lovász, Normal hypergraphs and perfect graph conjecture, Discrete Math. 2 (1972), no. 3, 253–267. https://doi.org/10.1016/0012-365X(72)90006-4
[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, AKCE Int. J. Graphs Comb. 21 (2024), no. 2, 189–197. https://doi.org/10.1080/09728600.2024.2329927
[9] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, USA, 2001.
Communications in Combinatorics and Optimization
Volume 11, Issue 1
March 2026
Pages 49-56

Files

Share

How to cite

Statistics