Irredundancy in multiple interval representations
type: Item
instance of: scholarly article
title: Irredundancy in multiple interval representations
zbMATH Open document ID: 0624.05060
DOI: 10.1016/0012-365X(87)90157-9
author: Edward Scheinerman
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A graph G is a t-interval graph if to each vertex of G we can assign (up to) t real intervals so that two vertices u and v of G are adjacent if and only if some interval assigned to u intersects an interval assigned to v. The interval number i(G) of a graph G is the least t for which G is a t-interval graph. Thus interval graphs are precisely those graphs G with \(i(G)=1\), and every graph is a t-interval graph for sufficiently large t. In a t-interval representation of a graph G, several intervals assigned to one vertex may meet several intervals assigned to one of its neighbors. Only one such intersection is required; the other are permitted, but are redundant. A t-interval representation, f: V(G)\(\to tI\), is irredundant if for each pair of adjacent vertices v and w, f(v)\(\cap f(w)\) is an interval. The irredundant interval number of G, \(i_ 0(G)\), is the least integer t such that G has an irredundant t- interval representation. Clearly \(i_ 0(G)\geq i(G)\). The paper presents methods of constructing graphs with \(i_ 0(G)=i(G)+1\). The main result shows that while \(i(G)=2\), \(i_ 0(G)\) can be arbitrary.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4012672
zbMATH Keywords: t-interval graph
zbMATH Keywords: interval number
zbMATH Keywords: t-interval representation of a graph
reviewed by: S. F. Kapoor
MaRDI profile type: Publication
cites work: Extremal values of the interval number of a graph. II
cites work: Extremal Values of the Interval Number of a Graph
cites work: The interval number of a complete multipartite graph
cites work: The interval number of a planar graph: Three intervals suffice
cites work: On double and multiple interval graphs
cites work: Recognizing graphs with fixed interval number is NP-complete
description: scientific article; zbMATH DE number 4012672