Colouring Semirandom Graphs

DOI10.1017/S0963548306007917zbMATH Open1137.05029MaRDI QIDQ5437231FDOQ5437231

Amin Coja-Oghlan

Publication date: 18 January 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Recommendations

• Automata, Languages and Programming
• Semirandom models as benchmarks for coloring algorithms
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time
• Solving NP-hard semirandom graph problems in polynomial expected time
• Heuristics for semirandom graph problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cited In (9)

• Constructing uniquely realizable graphs
• On the tractability of coloring semirandom graphs
• Heuristics for semirandom graph problems
• CsegGraph: a graph colouring instance generator
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Automata, Languages and Programming
• A note on semi-coloring of graphs
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time

This page was built for publication: Colouring Semirandom Graphs

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