Bounded color functions on graphs
David W. Matula · Networks · 1972
Abstract 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.