The distinguishing chromatic number (Q815210): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:17, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The distinguishing chromatic number |
scientific article |
Statements
The distinguishing chromatic number (English)
0 references
16 February 2006
0 references
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.
0 references