Almost all k-colorable graphs are easy to color
From MaRDI portal
Publication:3811723
DOI10.1016/0196-6774(88)90005-3zbMath0661.68066OpenAlexW2083883919MaRDI QIDQ3811723
Publication date: 1988
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(88)90005-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
A randomized algorithm for \(k\)-colorability ⋮ On independent sets in random graphs ⋮ Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ Expected complexity of graph partitioning problems ⋮ Simple decentralized graph coloring ⋮ Graphs with small chromatic numbers are easy to color ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Refining the phase transition in combinatorial search ⋮ Graph theoretic algorithm for automatic operation sequencing for progressive die design ⋮ Random I‐colorable graphs ⋮ Coloring k-colorable graphs in constant expected parallel time ⋮ A Simple SVD Algorithm for Finding Hidden Partitions ⋮ Coloring certain proximity graphs ⋮ Coloring random graphs ⋮ Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems ⋮ Complexity analysis of a decentralised graph colouring algorithm ⋮ A wide-ranging computational comparison of high-performance graph colouring algorithms ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ On the application of graph colouring techniques in round-robin sports scheduling ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ Approximation algorithm for maximum edge coloring ⋮ A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs
