EXTREMAL VALUES OF THE INTERVAL NUMBER OF A GRAPH .2.

被引：32

作者：

GRIGGS, JR

机构：

[1] Department of Mathematics, California Institute of Technology, Pasadena

来源：

DISCRETE MATHEMATICS | 1979年 / 28卷 / 01期

关键词：

D O I：

10.1016/0012-365X(79)90183-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that the interval number of a graph on n vertices is at most [ 1 4(n+1)], and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most [ 1 4(n+1)] finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K[n/2],[n/2]. © 1979.

引用

页码：37 / 47

页数：11

共 7 条

[1] INCIDENCE MATRICES AND INTERVAL GRAPHS [J].

FULKERSON, DR ;

GROSS, OA .

PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+

[2] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].

GILMORE, PC ;

HOFFMAN, AJ .

CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&

[3]

GRIGGS JR, UNPUBLISHED

[4]

Hajos G., 1957, INT MATH NACHR, V11, P65

[5]

Lekkerkerker C. G., 1962, FUND MATH, V51, P45, DOI DOI 10.4064/FM-51-1-45-64

[6]

MCGUIGAN R, 1977, JUN NSF CBMS C COLB

[7]

TROTTER WT, UNPUBLISHED

← 1 →