On the imaginary parts of chromatic root

2017/06/28 by Jason I. Brown, Brown, Jason I., David G. Wagner +1
Computer Science · Mathematics · #05C15 (Primary) #26C10 (Secondary) #Advanced Topology and Set Theory #Chromatic scale #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Order (exchange) #The Imaginary #Topological and Geometric Data Analysis #math.CO #msc:05C15 #msc:26C10

paper · pdf · doi:10.48550/arxiv.1706.09093

4 figures

arxiv created 2017/06/28 · openalex publication_date 2017/06/28 · arxiv updated 2017/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order n (that is, with n vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed p ∈ (0,1), almost every random graph G in the Erdös-Rényi model has a non-real root.

Citations

• Every planar map is four colorable. Part I: Discharging
• An introduction to chromatic polynomials
• Chromatic roots are dense in the whole complex plane
• A Zero-Free Interval for Chromatic Polynomials of Graphs

Related

• On the roots of hypergraph chromatic polynomials
• On the roots of Wiener polynomials of graphs
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• The oriented chromatic number of random graphs of bounded degree