The Library
Maximizing the number of q-colorings
Tools
Loh, P.-S., Pikhurko, Oleg and Sudakov, B. (2010) Maximizing the number of q-colorings. Proceedings of the London Mathematical Society, Vol.101 (No.3). pp. 655-696. doi:10.1112/plms/pdp041 ISSN 0024-6115 .
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1112/plms/pdp041
Abstract
Let PG(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 PG(4) over all planar graphs G. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing PG(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 that 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 < κq n2, where κq ≈ 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 ≤ n2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Proceedings of the London Mathematical Society | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 0024-6115 | ||||
Official Date: | November 2010 | ||||
Dates: |
|
||||
Volume: | Vol.101 | ||||
Number: | No.3 | ||||
Page Range: | pp. 655-696 | ||||
DOI: | 10.1112/plms/pdp041 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |