A sequential coloring algorithm for finite sets
type: Item
instance of: scholarly article
title: A sequential coloring algorithm for finite sets
zbMATH Open document ID: 0924.05023
DOI: 10.1016/S0012-365X(98)00340-9
author: Sanming Zhou
published in: Discrete Mathematics
publication date: 1999-11-03T00:00:00Z
review text: Let \(X\) be a finite set and \(P\) a hereditary property associated with the subsets of \(X\). A partition of \(X\) into \(n\) subsets each with property \(P\) is said to be a \(P\)-\(n\)-coloring of \(X\). The minimum \(n\) such that a \(P\)-\(n\)-coloring of \(X\) exists is defined to be the \(P\)-chromatic number of \(X\), denoted by \(\chi _{P}(X)\). The main purpose of this paper is to give an algorithm for sequentially \(P\)-coloring the finite set \(X\). By using this algorithm several upper bounds for \(\chi _{P}(X)\) are obtained; in particular, the well-known Welsh-Powell upper bound for the ordinary chromatic number is extended to the case of the \(P\)-chromatic number of any finite set. Also, the upper bounds obtained for \(P\)-chromatic numbers imply a theorem of the reviewer on the chromatic number of a hypergraph.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1321817
zbMATH Keywords: finite set
zbMATH Keywords: hereditary property
zbMATH Keywords: sequential coloring
zbMATH Keywords: conditional chromatic number
zbMATH Keywords: sequential coloring algorithm
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: The subchromatic number of a graph
cites work: Q4099676
cites work: Bounds for the chromatic number of a graph
cites work: On generalized graph colorings
cites work: Q5560916
cites work: The point-arboricity of a graph
cites work: An interpolation theorem for partitions which are complete with respect to hereditary properties
cites work: Q3760563
cites work: Q3220612
cites work: COVERING AND PACKING IN GRAPHS, I.
cites work: Hereditary properties of raphs
cites work: Q4175304
cites work: Bounds for the vertex linear arboricity
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: Chromatic partitions of a graph
cites work: Q5551307
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
cites work: Q5752591
cites work: Q3035307
cites work: Interpolation theorems for graphs, hypergraphs and matroids
Wikidata QID: Q126472656
full work available at URL: s0012-365x(98)00340-9
OpenAlex ID: W1977005762
description: scientific article; zbMATH DE number 1321817