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

Research output not available from this repository, contact author.

Request Changes to record.

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 > Mathematics
Journal or Publication Title:	Proceedings of the London Mathematical Society
Publisher:	Cambridge University Press
ISSN:	0024-6115
Official Date:	November 2010
Dates:	Date Event November 2010 Published
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