Tomescu's Graph Coloring Conjecture for \ell-Connected Graphs

DOI10.1137/19M1306646MaRDI QIDQ4997140zbMATH OpenOpenAlexWikidataFDO

Authors John Engbers, Aysel Erey, Jacob Fox, Xiaoyu He

Publication date 28 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.03236

zbMATH Keywords

graph coloringchromatic polynomialconnectivityTomescu's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k)lek!(k-1{)}^{n-k}$ for all connected graphs $G$ on $n$ vertices with chromatic number $kgeq4$. In this paper, we study the same problem with the additional constraint that $G$ is $ell$-connected. For $2$-connected graphs $G$, we prove a tight bound [ P_G(k) le (k-1)!((k-1)^{n-k+1} + (-1)^{n-k}), ] and show that equality is only achieved if $G$ is a $k$-clique with an ear attached. For $ellge3$, we prove an asymptotically tight upper bound [ P_G(k) le k!(k-1)^{n-ell - k + 1} + O((k-2)^n), ] and provide a matching lower bound construction. For the ranges $kgeqell$ or $ellgeq(k-2)(k-1)+1$ we further find the unique graph maximizing $P_G(k)$. We also consider generalizing $ell$-connected graphs to connected graphs with minimum degree $delta$.

Recommendations

• Upper bounds on the chromatic polynomial of a connected graph with fixed clique number
• scientific article; zbMATH DE number 1262192
• Some corollaries of a theorem of Whitney on the chromatic polynomial
• Maximum chromatic polynomials of 2‐connected graphs
• Maximizing the number of q -colorings
• The size of uniquely colorable graphs
• New bounds for chromatic polynomials and chromatic roots
• A proof of Tomescu's graph coloring conjecture
• Maximal chromatic polynomials of connected planar graphs
• An upper bound for the total chromatic number of dense graphs

Cites work

• scientific article; zbMATH DE number 1833089 (Why is no real title available?)
• scientific article; zbMATH DE number 3353319 (Why is no real title available?)
• A proof of Tomescu's graph coloring conjecture
• A reverse Sidorenko inequality
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Extremal \(H\)-colorings of trees and 2-connected graphs
• Extremal colorings and independent sets
• Maximal chromatic polynomials of connected planar graphs
• Maximising H-colourings of graphs
• Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree
• Maximizing proper colorings on graphs
• Maximizing the number of q -colorings
• Maximizing the number of x-colorings of 4-chromatic graphs
• Maximum chromatic polynomials of 2‐connected graphs
• Maximum number of colourings: 4-chromatic graphs
• Maximum number of colourings: 5-chromatic case
• New bounds for chromatic polynomials and chromatic roots
• On Independent Circuits Contained in a Graph
• On the maximum number of colorings of a graph
• On weighted graph homomorphisms
• The structure of k-chromatic graphs

Cited in

(5)

• Upper bounds on the chromatic polynomial of a connected graph with fixed clique number
• Maximum number of colourings: 5-chromatic case
• A proof of Tomescu's graph coloring conjecture
• Independence number and maximal chromatic polynomials of connected graphs
• Extremal graphs for Widom-Rowlinson colorings in k-chromatic graphs

This page was built for publication: Tomescu's Graph Coloring Conjecture for $\ell$-Connected Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997140)