Determining the Chromatic Number of a Graph

DOI10.1137/0208001zbMath0401.05043OpenAlexW2091593479MaRDI QIDQ4184859

Colin J. H. McDiarmid

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/468f35d86609ada6a7dce9b7234ceab774cb27a6

zbMATH Keywords

Chromatic Number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (14)

Bounds on the convex label number of trees ⋮ On the IO-complexity and approximation languages ⋮ Advice complexity of adaptive priority algorithms ⋮ Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph. ⋮ On the probable behaviour of some algorithms for finding the stability number of a graph ⋮ Minimum node covers and 2-bicritical graphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ A note on some computationally difficult set covering problems ⋮ Frozen development in graph coloring ⋮ On the span in channel assignment problems: Bounds, computing and counting ⋮ A simple branching scheme for vertex coloring problems ⋮ On the chromatic forcing number of a random graph ⋮ A note on the complexity of a partition algorithm ⋮ Achromatic numbers of random graphs

This page was built for publication: Determining the Chromatic Number of a Graph