Premium
The maximum interval number of graphs with given genus
Author(s) -
Scheinerman Edward R.
Publication year - 1987
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.3190110317
Subject(s) - mathematics , combinatorics , arboricity , discrete mathematics , pathwidth , interval (graph theory) , genus , indifference graph , graph , interval graph , chordal graph , outerplanar graph , planar graph , line graph , biology , botany
The interval number of a graph G , denoted i(G) , is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investigate the maximum value of the interval number for graphs with higher genus and show that the maximum value of the interval number of graphs with genus g is between ⌈√ g ⌉ and 3 + ⌈√3 g ⌉. We also show that the maximum arboricity of graphs with genus g is either 1 + ⌈√3 g ⌉ or 2 + ⌈√3 g ⌉.