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 条
  • [31] CHROMATIC NUMBER OF SKEW GRAPHS
    PAHLINGS, H
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (03) : 303 - 306
  • [32] COMPLEMENTARY GRAPHS AND THE CHROMATIC NUMBER
    Starr, Colin L.
    Turner, Galen E., III
    MISSOURI JOURNAL OF MATHEMATICAL SCIENCES, 2008, 20 (01) : 19 - 26
  • [33] On Indicated Chromatic Number of Graphs
    Raj, S. Francis
    Raj, R. Pandiya
    Patil, H. P.
    GRAPHS AND COMBINATORICS, 2017, 33 (01) : 203 - 219
  • [34] On the chromatic number of random graphs
    Coja-Oghlan, Amin
    Panagiotou, Konstantinos
    Steger, Angelika
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (05) : 980 - 993
  • [35] On the strong chromatic number of graphs
    Axenovich, Maria
    Martin, Ryan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (03) : 741 - 747
  • [36] Chromatic Number and Hamiltonicity of Graphs
    Li, Rao
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2020, 113 : 253 - 257
  • [37] On Group Chromatic Number of Graphs
    Hong-Jian Lai
    Xiangwen Li
    Graphs and Combinatorics, 2005, 21 : 469 - 474
  • [38] On the adaptable chromatic number of graphs
    Hell, Pavol
    Zhu, Xuding
    EUROPEAN JOURNAL OF COMBINATORICS, 2008, 29 (04) : 912 - 921
  • [39] On the chromatic number of random graphs
    Coja-Oghlan, Amin
    Panagiotou, Konstantinos
    Steger, Angelika
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2007, 4596 : 777 - +
  • [40] On incompactness for chromatic number of graphs
    Saharon Shelah
    Acta Mathematica Hungarica, 2013, 139 : 363 - 371
12345