Graphs with large distinguishing chromatic number
type: Item
instance of: scholarly article
title: Graphs with large distinguishing chromatic number
zbMATH Open document ID: 1266.05025
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i1p19
review text: Summary: The distinguishing chromatic number \(\chi_D(G)\) of a graph \(G\) is the minimum number of colours required to properly colour the vertices of \(G\) so that the only automorphism of \(G\) that preserves colours is the identity. For a graph \(G\) of order \(n\), it is clear that \(1\leq\chi_D(G)\leq n\), and it has been shown that \(\chi_D(G)=n\) if and only if \(G\) is a complete multipartite graph. This paper characterizes the graphs \(G\) of order \(n\) satisfying \(\chi_D(G)=n-1\) or \(\chi_D(G)=n-2\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 6171858
zbMATH Keywords: distinguishing chromatic number
zbMATH Keywords: distinguishing number
zbMATH Keywords: graph colouring
zbMATH Keywords: graph automorphism
author: M. Cavers
author: K. Seyffarth
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6171858