For (bull,claw)-, (bull,chair,C5)-, and (bull,claw,C5)-free graphs, the paper lists all structures that force chromatic number above 4 or 5, and gives a k-colorability criterion for clique expansions of odd cycles.
On the distinguishing chromatic number in hereditary graph classes
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The distinguishing chromatic number of a graph $G$, denoted $\chi_D(G)$, is the minimum number of colours in a proper vertex colouring of $G$ that is preserved by the identity automorphism only. Collins and Trenk proved that $\chi_D(G)\le 2\Delta(G)$ for any connected graph $G$, and the equality holds for complete balanced bipartite graphs $K_{p,p}$ and for $C_6$. In this paper, we show that the upper bound on $\chi_D(G)$ can be substantially reduced if we forbid some small graphs as induced subgraphs of $G$, that is, we study the distinguishing chromatic number in some hereditary graph classes.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
On $k$-colorability of $(bull, H)$-free graphs
For (bull,claw)-, (bull,chair,C5)-, and (bull,claw,C5)-free graphs, the paper lists all structures that force chromatic number above 4 or 5, and gives a k-colorability criterion for clique expansions of odd cycles.