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 条
  • [21] On the chromatic number of Toeplitz graphs
    Nicoloso, Sara
    Pietropaoli, Ugo
    DISCRETE APPLIED MATHEMATICS, 2014, 164 : 286 - 296
  • [22] The Robust Chromatic Number of Graphs
    Bacso, Gabor
    Patkos, Balazs
    Tuza, Zsolt
    Vizer, Mate
    GRAPHS AND COMBINATORICS, 2024, 40 (04)
  • [23] MONOTONE CHROMATIC NUMBER OF GRAPHS
    Saleh, Anwar
    Muthana, Najat
    Al-Shammakh, Wafa
    Alashwali, Hanaa
    INTERNATIONAL JOURNAL OF ANALYSIS AND APPLICATIONS, 2020, 18 (06): : 1108 - 1122
  • [24] Hat chromatic number of graphs
    Bosek, Bartlomiej
    Dudek, Andrzej
    Farnik, Michal
    Grytczuk, Jaroslaw
    Mazur, Przemyslaw
    DISCRETE MATHEMATICS, 2021, 344 (12)
  • [25] On Indicated Chromatic Number of Graphs
    S. Francis Raj
    R. Pandiya Raj
    H. P. Patil
    Graphs and Combinatorics, 2017, 33 : 203 - 219
  • [26] Chromatic number and subtrees of graphs
    Baogang Xu
    Yingli Zhang
    Frontiers of Mathematics in China, 2017, 12 : 441 - 457
  • [27] On the harmonious chromatic number of graphs
    Araujo-Pardo, Gabriela
    Montellano-Ballesteros, Juan Jose
    Olsen, Mika
    Rubio-Montiel, Christian
    BOLETIN DE LA SOCIEDAD MATEMATICA MEXICANA, 2024, 30 (02):
  • [28] On the chromatic number of tree graphs
    Estivill-Castro, V
    Noy, M
    Urrutia, J
    DISCRETE MATHEMATICS, 2000, 223 (1-3) : 363 - 366
  • [29] Chromatic number and subtrees of graphs
    Xu, Baogang
    Zhang, Yingli
    FRONTIERS OF MATHEMATICS IN CHINA, 2017, 12 (02) : 441 - 457
  • [30] The chromatic number of oriented graphs
    Sopena, E
    JOURNAL OF GRAPH THEORY, 1997, 25 (03) : 191 - 205
12345