Achromatic numbers and graph operations
type: Item
instance of: scholarly article
title: Achromatic numbers and graph operations
zbMATH Open document ID: 0760.05040
DOI: 10.1016/0012-365X(92)90683-7
author: Pavol Hell
author: Donald J. Miller
published in: Discrete Mathematics
publication date: 1993-01-17T00:00:00Z
review text: Many papers have been written on colourings and chromatic numbers, but not so many ones on achromatic numbers. While the chromatic number of a given graph \(X\) is the smallest \(n\) for which \(X\) admits a complete \(n\)- colouring, the achromatic number is the largest one with the same property. The authors study this branch of graph theory. They investigate the achromatic number of the disjoint union of graphs and the best possible lower bound for the categorical product of graphs. On the other hand, they show a surprising example of two graphs both with achromatic number exactly \(a\) such that their product has achromatic number approximately equal to \((a)^{a^ 2/2}\). Finally the authors show that the achromatic number of the product of graphs is bounded above.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 97510
zbMATH Keywords: achromatic number
zbMATH Keywords: product of graphs
zbMATH Keywords: union of graphs
reviewed by: Jiri Vinarek
MaRDI profile type: Publication
cites work: On the chromatic number of the product of graphs
cites work: The chromatic number of the product of two 4-chromatic graphs is 4
cites work: On multiplicative graphs and the product conjecture
cites work: Q4097314
cites work: Graph with given achromatic number
cites work: Q5621382
cites work: A lower estimate for the achromatic number of irreducible graphs
cites work: Q4083463
full work available at URL: 0012-365x(92)90683-7
OpenAlex ID: W2027719300
Recommended article: Q3320413
Recommended article: Achromatic numbers for circulant graphs and digraphs
Recommended article: Concerning the achromatic number of graphs
Recommended article: Q3216676
Recommended article: Q3110148
Recommended article: The achromatic colouring of graphs
Recommended article: Chromatic numbers in some graphs
Recommended article: Achromatic numbers of Kneser graphs
Recommended article: Q4364806
Recommended article: Q3984024
description: scientific article; zbMATH DE number 97510