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

共 6 条

[1]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[2] ON CHAIN AND ANTI-CHAIN FAMILIES OF A PARTIALLY ORDERED SET [J].

FRANK, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 29 (02) :176-184

[3]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[4] TOLERANCE GRAPHS [J].

GOLUMBIC, MC ;

MONMA, CL ;

TROTTER, WT .

DISCRETE APPLIED MATHEMATICS, 1984, 9 (02) :157-170

[5]

GOLUMBIC MC, 1982, UTILITAS MATHEMATICA, V35, P321

[6] THE ELLIPSOID METHOD AND ITS CONSEQUENCES IN COMBINATORIAL OPTIMIZATION [J].

GROTSCHEL, M ;

LOVASZ, L ;

SCHRIJVER, A .

COMBINATORICA, 1981, 1 (02) :169-197

← 1 →