What type of study is this?

This is a Experimental Study study.

October 13, 2025Open Access

The List-distinguishing chromatic number of graphs containing only small complete bigraphs

Key Points

Improved upper bounds establish a critical advancement in determining distinguishing chromatic numbers for various graph types, leading to clearer applications.
Key results apply Menger's theorem to explore implications for graphs associated with Paley graphs, revealing structural insights.
Connected graphs with small complete bigraphs as induced subgraphs exhibit significant characteristics influencing chromatic distinctions.
These findings emphasize potential applications in graph theory and combinatorial designs, with broader future research opportunities.

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, Cayley graphs on Dihedral groups, and circulant Cayley graphs.

Ask AI

Helpful

Bookmark

View Full Paper