Colouring Semirandom Graphs

DOI10.1017/S0963548306007917MaRDI QIDQ5437231zbMATH OpenFDO

Authors Amin Coja-Oghlan

Publication date 18 January 2008

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

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)

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

Cited in

(10)

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

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)