On the interval number of random graphs
type: Item
instance of: scholarly article
title: On the interval number of random graphs
zbMATH Open document ID: 0712.05049
DOI: 10.1016/0012-365X(90)90050-R
author: Edward Scheinerman
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: The interval number of a graph G is defined as the smallest integer t such that G is an intersection graph of sets each of which is the union of t real intervals. The interval number is shown to be asymptotically equal to (n log 2)/(2 log n) for almost every graph.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 4170954
zbMATH Keywords: multiple interval representation
zbMATH Keywords: interval number
zbMATH Keywords: intersection graph
MaRDI profile type: Publication
cites work: On an extremal problem concerning the interval number of a graph
cites work: On the Interval Number of a Triangulated Graph
cites work: On the unit interval number of a graph
cites work: Weighted sums of certain dependent random variables
cites work: A note on the interval number of a graph
cites work: On tail probabilities for martingales
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: Some results about the interval number of a graph
cites work: Irrepresentability by multiple intersection, or why the interval number is unbounded
cites work: Irredundancy in multiple interval representations
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 4170954