Deciding 3-colourability in less than O(1.415n) steps

DOI10.1007/3-540-57899-4_51zbMath1530.05182MaRDI QIDQ6143975

Ingo Schiermeyer

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexitygraph algorithm\(k\)-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the complexity of the chromatic number problem
• The Complexity of Near-Optimal Graph Coloring
• An algorithm for the chromatic number of a graph
• On cliques in graphs
• The NP-completeness column: An ongoing guide

This page was built for publication: Deciding 3-colourability in less than O(1.415n) steps