Premium
On double and multiple interval graphs
Author(s) -
Trotter William T.,
Harary Frank
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030302
Subject(s) - combinatorics , mathematics , bipartite graph , interval graph , discrete mathematics , interval (graph theory) , vertex (graph theory) , graph , line graph , pathwidth
In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f ( u ) of the real line so that f ( u ) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f ( u ) and f ( v )meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K m, n has interval number ⌈( mn + 1)/( m + n )⌉.