Premium
Bounded color functions on graphs
Author(s) -
Matula D. W.
Publication year - 1972
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230020104
Subject(s) - bounded function , combinatorics , mathematics , vertex (graph theory) , chromatic scale , graph , upper and lower bounds , discrete mathematics , mathematical analysis
The maximum edge‐connectivity of any subgraph plus unity is shown to be an upper bound on the chromatic number for any graph. More generally it is shown that every graph possesses a Grundy function bounded at each vertex by the maximum edge‐connectivity of the subgraphs containing that vertex. A discussion of how to construct such a Grundy function is also provided.