Mathematics – Combinatorics
Scientific paper
2008-11-17
Mathematics
Combinatorics
44 pages + 9 page appendix of Mathematica computations; minor revisions
Scientific paper
Let P_G(q) denote the number of proper q-colorings of a graph G. This function, called the chromatic polynomial of G, was introduced by Birkhoff in 1912, who sought to attack the famous four-color problem by minimizing P_G(4) over all planar graphs G. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing P_G(q) over various families of graphs. In this paper, we study an old problem of Linial and Wilf, to find the graphs with n vertices and m edges which maximize the number of q-colorings. We provide the first approach which enables one to solve this problem for many nontrivial ranges of parameters. Using our machinery, we show that for each q >= 4 and sufficiently large m < \kappa_q n^2 where \kappa_q is approximately 1/(q log q), the extremal graphs are complete bipartite graphs minus the edges of a star, plus isolated vertices. Moreover, for q = 3, we establish the structure of optimal graphs for all large m <= n^2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989.
Loh Po-Shen
Pikhurko Oleg
Sudakov Benny
No associations
LandOfFree
Maximizing the number of q-colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximizing the number of q-colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing the number of q-colorings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466369