On the order of uniquely (k,m)-colourable graphs
type: Item
instance of: scholarly article
title: On the order of uniquely (k,m)-colourable graphs
zbMATH Open document ID: 0712.05024
DOI: 10.1016/0012-365X(90)90200-2
author: Izak Broere
author: Marietjie Frick
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: An m-admissible colouring of a finite simple graph G is a colouring of the vertices of G such that no m-clique of G is monocoloured. The m-th chromatic number of G is the least number \(\chi_ m(G)\) of colours such that G has an \(\chi_ m(G)\)-admissible colouring. A graph is called uniquely (k,m)-colourable if all m-admissible colourings in k colours induce the same partition of the vertex set of G. For \(k\geq 2\) and \(m\geq 3\), there exists a uniquely (k,m)-colourable graph of order n iff \(n\geq k(m-1)+m(k-1)\). All uniquely (2,m)-colourable graphs of order 3m-2 are determined, and the structure of all uniquely (k,m)- colourable graphs of order \(k(m-1)+m(k-1)\) is described.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4170929
zbMATH Keywords: m-admissible colouring
zbMATH Keywords: uniquely (k,m)-colourable graph
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: Q4187840
cites work: Q3781778
cites work: Q4873798
cites work: Q3284375
cites work: A Theorem on k-Saturated Graphs
cites work: Uniquely colorable graphs
cites work: Some covering concepts in graphs
full work available at URL: 0012-365x(90)90200-2
OpenAlex ID: W1966409080
description: scientific article; zbMATH DE number 4170929