An algorithm for the chromatic number of a graph

DOI10.1093/COMJNL/14.1.38zbMath0215.05601OpenAlexW2133732980MaRDI QIDQ5617637

Nicos Christofides

Publication date: 1971

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/14.1.38

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (26)

Data parallel computing for network-structured optimization problems ⋮ A graph coloring algorithm for large scale scheduling problems ⋮ PARALLELIZATION STRATEGIES OF A ROW-ACTION METHOD FOR MULTICOMMODITY NETWORK FLOW PROBLEMS ⋮ Matchings in simplicial complexes, circuits and toric varieties ⋮ Efficient bounds on a branch and bound algorithm for graph colouration ⋮ Graph theoretic algorithm for automatic operation sequencing for progressive die design ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ Clique detection for nondirected graphs: Two new algorithms ⋮ An approximation algorithm for 3-Colourability ⋮ Deciding 3-colourability in less than O(1.415n) steps ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ On the equality of the partial Grundy and upper ochromatic numbers of graphs ⋮ Chromatic optimisation: Limitations, objectives, uses, references ⋮ Co-2-plex vertex partitions ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Enumerating maximal independent sets with applications to graph colouring. ⋮ An algorithm for obtaining the chromatic number and an optimal coloring of a graph ⋮ An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring ⋮ A note on the complexity of the chromatic number problem ⋮ Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7 ⋮ Unnamed Item ⋮ Faster graph coloring in polynomial space ⋮ A search space ``cartography for guiding graph coloring heuristics ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ A new backtracking algorithm for generating the family of maximal independent sets of a graph ⋮ A method of synthesis of linear discriminant function in the case of nonseparability

This page was built for publication: An algorithm for the chromatic number of a graph