Minimal Obstructions for Partial Representations of Interval Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F18%3A00500501" target="_blank" >RIV/67985807:_____/18:00500501 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/18:00328800
Result on the web
<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p55</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Minimal Obstructions for Partial Representations of Interval Graphs
Original language description
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1077-8926
e-ISSN
—
Volume of the periodical
25
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
49
Pages from-to
—
UT code for WoS article
000456788300010
EID of the result in the Scopus database
2-s2.0-85061618360