Cover-incomparability graphs of posets

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15027289
ISSN:	0167-8094
Št. ogledov:	29
Št. prenosov:	5
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni povzetek:	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:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 335-347
Letnik:	ǂVol. ǂ25
Zvezek:	ǂno. ǂ4
Čas izdaje:	2008
ID:	1474073