Relaxed chromatic numbers of graphs |
| |
Authors: | Margaret L Weaver Douglas B West |
| |
Institution: | (1) Eastern Illinois University, 61920 Charleston, IL, USA;(2) University of Illinois, 61801-2975 Urbana, IL, USA |
| |
Abstract: | Given any family of graphsP, theP chromatic number
p
(G) of a graphG is the smallest number of classes into whichV(G) can be partitioned such that each class induces a subgraph inP. We study this for hereditary familiesP of two broad types: the graphs containing no subgraph of a fixed graphH, and the graphs that are disjoint unions of subgraphs ofH. We generalize results on ordinary chromatic number and we computeP chromatic number for special choices ofP on special classes of graphs.Research supported in part by ONR Grant N00014-85K0570 and by a grant from the University of Illinois Research Board. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|