Distance perfectness of graphs
Discussiones Mathematicae Graph Theory (1999)
- Volume: 19, Issue: 1, page 31-43
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topAndrzej Włoch. "Distance perfectness of graphs." Discussiones Mathematicae Graph Theory 19.1 (1999): 31-43. <http://eudml.org/doc/270437>.
@article{AndrzejWłoch1999,
abstract = {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].},
author = {Andrzej Włoch},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {perfect graphs; strongly perfect graphs; chromatic number; -distance clique; -stable transversal; -distance chromatic number; partition; perfectness},
language = {eng},
number = {1},
pages = {31-43},
title = {Distance perfectness of graphs},
url = {http://eudml.org/doc/270437},
volume = {19},
year = {1999},
}
TY - JOUR
AU - Andrzej Włoch
TI - Distance perfectness of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 1
SP - 31
EP - 43
AB - 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].
LA - eng
KW - perfect graphs; strongly perfect graphs; chromatic number; -distance clique; -stable transversal; -distance chromatic number; partition; perfectness
UR - http://eudml.org/doc/270437
ER -
References
top- [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 Zbl0857.05037
- [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. Zbl0165.57302
- [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. Zbl0239.05111
- [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. Zbl0806.05052
- [7] H. Müller, On edge perfectness and class of bipartite graphs, Discrete Math. 148 (1996) 159-187. Zbl0844.68095
- [8] G. Ravindra, Meyniel's graphs are strongly perfect, Ann. Discrete Math. 21 (1984) 145-148.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.