In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1083,
author = {Andrzej W\l och},
title = {Distance perfectness of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {19},
year = {1999},
pages = {31-43},
zbl = {0933.05063},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1083}
}
Andrzej Włoch. Distance perfectness of graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 31-43. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1083/
[000] [1] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
[001] [2] C. Berge and P. Duchet, Strongly perfect graphs, Ann. Discrete Math. 21 (1984) 57-61.
[002] [3] A.L. Cai and D. Corneil, A generalization of perfect graphs - i-perfect graphs, J. Graph Theory 23 (1996) 87-103, doi: 10.1002/(SICI)1097-0118(199609)23:1<87::AID-JGT10>3.0.CO;2-H | Zbl 0857.05037
[003] [4] F. Kramer and H. Kramer, Un Probléme de coloration des sommets d'un gráphe, C.R. Acad. Sc. Paris, 268 Serie A (1969) 46-48. | Zbl 0165.57302
[004] [5] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253-267, doi: 10.1016/0012-365X(72)90006-4. | Zbl 0239.05111
[005] [6] F. Maffray and M. Preissmann, Perfect graphs with no P₅ and no K₅, Graphs and Combin. 10 (1994) 173-184, doi: 10.1007/BF02986662. | Zbl 0806.05052
[006] [7] H. Müller, On edge perfectness and class of bipartite graphs, Discrete Math. 148 (1996) 159-187. | Zbl 0844.68095
[007] [8] G. Ravindra, Meyniel's graphs are strongly perfect, Ann. Discrete Math. 21 (1984) 145-148.