Cover-incomparability graphs of posets

Boštjan Brešar (Author), Manoj Changat (Author), Sandi Klavžar (Author), Matjaž Kovše (Author), Joseph Mathews (Author), Antony Mathews (Author)

Abstract

Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, katerih CI-graf je tetiven (razdaljno-hereditaren, ptolemajski) in predlagamo splošen pristop k obravnavi CI-grafov. Predstavimo tudi več odprtih problemov.

Keywords

matematika;teorija grafov;delno urejena množica;temeljni graf;tranzitna funkcija;tetiven graf;razdaljno-hereditaren graf;mathematics;graph theory;poset;underlying graph;transit function;chordal graph;distance-hereditary graph;claw;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	15027289
ISSN:	0167-8094
Views:	29
Downloads:	5
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary abstract:	Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 335-347
Volume:	ǂVol. ǂ25
Issue:	ǂno. ǂ4
Chronology:	2008
ID:	1474073