Between 2- and 3-colorability

zbMath1307.05203arXiv1404.4987MaRDI QIDQ5919171

Alan M. Frieze, Wesley Pegden

Publication date: 19 February 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.4987

zbMATH Keywords

random graphshomomorphisms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Homomorphism complexes and \(k\)-cores

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A note on the sharp concentration of the chromatic number of random graphs
• Random cubic graphs are not homomorphic to the cycle of size 7
• On tree census and the giant component in sparse random graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Almost all graphs with average degree 4 are 3-colorable
• The two possible values of the chromatic number of a random graph
• Circular chromatic number: A survey

This page was built for publication: Between 2- and 3-colorability