The List-distinguishing chromatic number of graphs containing only small complete bigraphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918141232152576 |
|---|---|
| author | Banerjee, Amitayu |
| author_facet | Banerjee, Amitayu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11992 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The List-distinguishing chromatic number of graphs containing only small complete bigraphs Banerjee, Amitayu Combinatorics Group Theory 05C15, 05C25 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. |
| title | The List-distinguishing chromatic number of graphs containing only small complete bigraphs |
| topic | Combinatorics Group Theory 05C15, 05C25 |
| url | https://arxiv.org/abs/2509.11992 |