Using stable sets to bound the chromatic number

被引：3
作者：
de Werra, D [1 ]
Hansen, P
机构：
[1] Ecole Polytech Fed Lausanne, Inst Math, CH-1015 Lausanne, Switzerland
[2] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada
[3] Ecole Hautes Etud Commerciales, Dept Methods Quantitat Gest, Montreal, PQ, Canada
来源：
INFORMATION PROCESSING LETTERS | 2003年 / 87卷 / 03期
基金：
加拿大自然科学与工程研究理事会;
关键词：
graph coloring; chromatic number; stable set; longest path; algorithms;
D O I：
10.1016/S0020-0190(03)00266-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A generalization of the Roy-Gallai theorem is presented: it is based on the existence in any oriented graph of a stable set S such that for any node omega not in S there is an elementary path from some node of S to omega. The bound obtained improves earlier results by Berge and by Li. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：127 / 131
页数：5
相关论文
共 13 条
  • [1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [2] DIPERFECT GRAPHS
    BERGE, C
    [J]. COMBINATORICA, 1982, 2 (03) : 213 - 222
  • [3] Berge C, 1973, GRAPHS HYPERGRAPHS
  • [4] ON CONJECTURES OF GRAFFITI
    FAJTLOWICZ, S
    [J]. DISCRETE MATHEMATICS, 1988, 72 (1-3) : 113 - 118
  • [5] FAJTLOWICZ S, 1999, WRITTEN WALL VERSION
  • [6] Gallai T, 1968, THEORY GRAPHS, V38, P115
  • [7] Mixed graph colorings
    Hansen, P
    Kuplinsky, J
    De Werra, D
    [J]. MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 1997, 45 (01) : 145 - 160
  • [8] HANSEN P, 2002, AIDING DECISIONS MUL, P23
  • [9] A generalization of the Gallai-Roy theorem
    Li, H
    [J]. GRAPHS AND COMBINATORICS, 2001, 17 (04) : 681 - 685
  • [10] ROY B, 1967, REV INFO RECH OPER, V5, P129
12