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