Determining the Chromatic Number of a Graph

DOI10.1137/0208001MaRDI QIDQ4184859zbMATH OpenOpenAlexFDO

Authors Colin 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

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

Cited in

(15)

• Bounds on the convex label number of trees
• On the IO-complexity and approximation languages
• On the span in channel assignment problems: Bounds, computing and counting
• On the chromatic forcing number of a random graph
• 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
• A note on some computationally difficult set covering problems
• Achromatic numbers of random graphs
• Graph theory (algorithmic, algebraic, and metric problems)
• Frozen development in graph coloring
• Advice complexity of adaptive priority algorithms
• A hard problem that is almost always easy
• A simple branching scheme for vertex coloring problems
• A note on the complexity of a partition algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4184859)