skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
Award ID(s):
1800681
PAR ID:
10300414
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Discrete Mathematics
Volume:
343
Issue:
10
ISSN:
0012-365X
Page Range / eLocation ID:
111989
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 McDiarmid, Mitsche and Prałat noted that around  the clique chromatic number of the random graph  changes by  when we increase the edge‐probability  by , but left the details of this surprising “jump” phenomenon as an open problem. We settle this problem, that is, resolve the nature of this polynomial “jump” of the clique chromatic number of the random graph  around edge‐probability . Our proof uses a mix of approximation and concentration arguments, which enables us to (i) go beyond Janson's inequality used in previous work and (ii) determine the clique chromatic number of  up to logarithmic factors for any edge‐probability . 
    more » « less