The distinguishing chromatic number
type: Item
instance of: scholarly article
title: The distinguishing chromatic number
zbMATH Open document ID: 1081.05033
author: Karen L. Collins
author: Ann Trenk
published in: The Electronic Journal of Combinatorics
publication date: 2006-02-16T00:00:00Z
full work available at URL: https://eudml.org/doc/125578
full work available at URL: v13i1r16.html
review text: Summary: In this paper we define and study the distinguishing chromatic number, \(\chi_D(G)\), of a graph \(G\), building on the work of \textit{M. O. Albertson} and \textit{K. L. Collins} [Electron. J. Comb. 3, Research paper R18 (1996); printed version J. Comb. 3, 259--275 (1996; Zbl 0851.05088)] who studied the distinguishing number. We find \(\chi_D(G)\) for various families of graphs and characterize those graphs with \(\chi_D(G) = |V(G)|\), and those trees with the maximum chromatic distingushing number for trees. We prove analogs of Brooks' theorem for both the distinguishing number and the distinguishing chromatic number, and for both trees and connected graphs. We conclude with some conjectures.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 5006929
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5006929