Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
417879 | Discrete Applied Mathematics | 2016 | 10 Pages |
Abstract
We give some extremal properties on the number B(G)B(G) of non-equivalent ways of coloring a given graph GG, also known as the (graphical) Bell number of GG. In particular, we study bounds on B(G)B(G) for graphs with a maximum degree constraint. First, an upper bound on B(G)B(G) is given for graphs with fixed order nn and maximum degree ΔΔ. Then, we give lower bounds on B(G)B(G) for fixed order nn and maximum degree 1, 2, n−2n−2 and n−1n−1. In each case, the bound is tight and we describe all graphs that reach the bound with equality.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alain Hertz, Hadrien Mélot,