An algorithm for the chromatic number of a graph

DOI10.1093/COMJNL/14.1.38MaRDI QIDQ5617637zbMATH OpenOpenAlexFDO

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

Cited in

(27)

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

This page was built for publication: An algorithm for 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 Q5617637)