INTERVAL COMPETITION GRAPHS OF SYMMETRICAL DIGRAPHS

Authors
LUNDGREN JR RASMUSSEN CW MAYBEE JS
Citation
Jr. Lundgren et al., INTERVAL COMPETITION GRAPHS OF SYMMETRICAL DIGRAPHS, Discrete mathematics, 119(1-3), 1993, pp. 113-122
Citations number
13
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
119
Issue
1-3
Year of publication
1993
Pages
113 - 122
Database
ISI
SICI code
0012-365X(1993)119:1-3<113:ICGOSD>2.0.ZU;2-Z
Abstract
The competition graph of a loopless symmetric digraph H is the two-ste p qraph, S2(H). Necessary and sufficient conditions on H are given for S2(H) to be interval or unit interval. These are useful properties wh en application requires that the competition graph be efficiently colo rable. Computational aspects are discussed, as are related open proble ms.