Cover-incomparability graphs and chordal graphs

Boštjan Brešar (Author), Manoj Changat (Author), Tanja Gologranc (Author), Joseph Mathews (Author), Antony Mathews (Author)

Abstract

Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti.

Keywords

matematika;teorija grafov;delno urejena množica;temeljni graf;tetiven graf;razcepljen graf;bločni graf;mathematics;graph theory;poset;underlying graph;chordal graph;split graf;block graph;

Data

Language:	English
Year of publishing:	2010
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	15656537
ISSN:	0166-218X
Views:	38
Downloads:	14
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Grafi pokritij-neprimerljivosti in tetivni grafi
Secondary abstract:	The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1752-1759
Volume:	Vol. 158
Issue:	iss. 16
Chronology:	2010
ID:	1475206