ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 19(1) (1999) 31-43
DOI: 10.7151/dmgt.1083


Andrzej Włoch

Department of Mathematics
Technical University of Rzeszów
ul. W. Pola 2, 35-959 Rzeszów



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].

Keywords: perfect graphs, strongly perfect graphs, chromatic number.

1991 Mathematics Subject Classification: 05C75, 05C60.


[1] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
[2] C. Berge and P. Duchet, Strongly perfect graphs, Ann. Discrete Math. 21 (1984) 57-61.
[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.
[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.
[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.
[6] F. Maffray and M. Preissmann, Perfect graphs with no P5 and no K5, Graphs and Combin. 10 (1994) 173-184, doi: 10.1007/BF02986662.
[7] H. Müller, On edge perfectness and class of bipartite graphs, Discrete Math. 148 (1996) 159-187.
[8] G. Ravindra, Meyniel's graphs are strongly perfect, Ann. Discrete Math. 21 (1984) 145-148.

Received 11 March 1998
Revised 11 January 1999