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)

Full work available at URL https://doi.org/10.1017/S0963548306007917

Mathematics Subject Classification ID

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

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

(11)

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

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)