STABILITY NUMBER AND CHROMATIC NUMBER OF TOLERANCE GRAPHS

被引：8
|
作者：
NARASIMHAN, G
MANBER, R
机构：
[1] Computer Sciences Department, University of Wisconsin-Madison, Madison
来源：
DISCRETE APPLIED MATHEMATICS | 1992年 / 36卷 / 01期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0166-218X(92)90203-M
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Golumbic and Monma [3] introduced a subclass of perfect graphs called tolerance graphs. In this paper, we present algorithms to compute the stability number, the clique number, the chromatic number, and the clique cover number of a tolerance graph.
引用
收藏
页码：47 / 56
页数：10
相关论文
共 50 条
  • [41] THE CHROMATIC NUMBER OF RANDOM GRAPHS
    BOLLOBAS, B
    COMBINATORICA, 1988, 8 (01) : 49 - 55
  • [42] On the chromatic number of circulant graphs
    Barajas, Javier
    Serra, Oriol
    DISCRETE MATHEMATICS, 2009, 309 (18) : 5687 - 5696
  • [43] THE CHROMATIC NUMBER OF RANDOM GRAPHS
    LUCZAK, T
    COMBINATORICA, 1991, 11 (01) : 45 - 54
  • [44] On the chromatic number of disk graphs
    Malesinska, E
    Piskorz, S
    Weissenfels, G
    NETWORKS, 1998, 32 (01) : 13 - 22
  • [45] On the injective chromatic number of graphs
    Hahn, G
    Kratochvíl, J
    Sirán, J
    Sotteau, D
    DISCRETE MATHEMATICS, 2002, 256 (1-2) : 179 - 192
  • [46] ON THE DYNAMIC CHROMATIC NUMBER OF GRAPHS
    Akbari, S.
    Ghanbari, M.
    Jahanbekam, S.
    COMBINATORICS AND GRAPHS, 2010, 531 : 11 - +
  • [47] ON THE CHROMATIC NUMBER OF THE PRODUCT OF GRAPHS
    DUFFUS, D
    SANDS, B
    WOODROW, RE
    JOURNAL OF GRAPH THEORY, 1985, 9 (04) : 487 - 495
  • [48] The list chromatic number of graphs with small clique number
    Molloy, Michael
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 264 - 284
  • [49] Graphs whose choice number is equal to their chromatic number
    Gravier, S
    Maffray, F
    JOURNAL OF GRAPH THEORY, 1998, 27 (02) : 87 - 97
  • [50] CHROMATIC NUMBER VERSUS COCHROMATIC NUMBER IN GRAPHS WITH BOUNDED CLIQUE NUMBER
    ERDOS, P
    GIMBEL, J
    STRAIGHT, HJ
    EUROPEAN JOURNAL OF COMBINATORICS, 1990, 11 (03) : 235 - 240
12345