An upper bound for the list-distinguishing chromatic number of K r,r+1-free graphs
math.CO, math.GR
Submitted: 2025-09-15
Updated: 2026-10-28
Comments: Presented in ICGTA 2025 (International Conference on Graph Theory and Its Applications 2025), Comments are welcome, Revised version, 10 pages, 3 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: In 2006, Collins and Trenk obtained a general sharp upper bound for the distinguishing chromatic number of a connected graph.
Terminology
Abstract
In 2006, Collins and Trenk obtained a general sharp upper bound for the distinguishing chromatic number of a connected graph. Inspired by Catlin's combinatorial techniques from 1978, we establish improved upper bounds for classes of connected graphs that have only small complete bigraphs as induced subgraphs. In this framework, we also consider the list-distinguishing chromatic number of such graphs. We apply Menger's theorem to demonstrate applications of our main result for graphs whose constructions are based on Paley graphs and Cayley graphs on Dihedral groups.
Sources
- Distinguishing chromatic number of middle and subdivision graphs
- On the distinguishing chromatic number in hereditary graph classes
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality