Distance perfectness of graphs

• Autorzy: Andrzej Włoch
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

perfect graphs; strongly perfect graphs; chromatic number

Kategorie tematyczne

• 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1999
• Tom: 19
• Numer: 1
• Strony: 31-43

Daty

wydano

1999

otrzymano

1998-03-11

poprawiono

1999-01-11

Twórcy

autor

Andrzej Włoch

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

Bibliografia

• [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 P₅ and no K₅, 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.

Identyfikatory

DOI

10.7151/dmgt.1083