Irredundancy in multiple interval representations (Q1092070): Difference between revisions

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.