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 条
  • [1] On the chromatic vertex stability number of graphs
    Akbari, Saieed
    Beikmohammadi, Arash
    Klavzar, Sandi
    Movarraei, Nazanin
    EUROPEAN JOURNAL OF COMBINATORICS, 2022, 102
  • [2] On the Chromatic Edge Stability Number of Graphs
    Arnfried Kemnitz
    Massimiliano Marangio
    Nazanin Movarraei
    Graphs and Combinatorics, 2018, 34 : 1539 - 1551
  • [3] On the Chromatic Edge Stability Number of Graphs
    Kemnitz, Arnfried
    Marangio, Massimiliano
    Movarraei, Nazanin
    GRAPHS AND COMBINATORICS, 2018, 34 (06) : 1539 - 1551
  • [4] On the total chromatic edge stability number and the total chromatic subdivision number of graphs
    Kemnitz, Arnfried
    Marangio, Massimiliano
    DISCRETE MATHEMATICS LETTERS, 2022, 10 : 1 - 8
  • [5] On the edge chromatic vertex stability number of graphs
    Alikhani, Saeid
    Piri, Mohammad R.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2023, 20 (01) : 29 - 34
  • [6] On the chromatic number of graphs
    Butenko, S
    Festa, P
    Pardalos, PM
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2001, 109 (01) : 51 - 67
  • [7] On the Chromatic Number of Graphs
    S. Butenko
    P. Festa
    P. M. Pardalos
    Journal of Optimization Theory and Applications, 2001, 109 (1) : 69 - 83
  • [8] Graphs whose circular chromatic number equals the chromatic number
    Zhu, XD
    COMBINATORICA, 1999, 19 (01) : 139 - 149
  • [9] The difference between game chromatic number and chromatic number of graphs
    Matsumoto, Naoki
    INFORMATION PROCESSING LETTERS, 2019, 151
  • [10] Graphs Whose Circular Chromatic Number Equals the Chromatic Number
    Xuding Zhu
    Combinatorica, 1999, 19 : 139 - 149
12345