English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 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    n  2 , 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  ⩽  n  2 /4, confirming (in a stronger form) a conjecture of Lazebnik from 1989.

Maximizing the number of q ‐colorings