Premium
The chromatic covering number of a graph
Author(s) -
Naserasr Reza,
Tardif Claude
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20127
Subject(s) - chromatic scale , combinatorics , mathematics , graph , vertex (graph theory) , windmill graph , friendship graph , critical graph , discrete mathematics , graph power , line graph
Following [1], we investigate the problem of covering a graph G with induced subgraphs G 1 ,…, G k of possibly smaller chromatic number, but such that for every vertex u of G , the sum of reciprocals of the chromatic numbers of the G i 's containing u is at least 1. The existence of such “chromatic coverings” provides some bounds on the chromatic number of G . © 2005 Wiley Periodicals, Inc.