Kolmogorov random graphs only have trivial stable colorings.

DOI10.1016/S0020-0190(01)00206-XzbMath1050.68051MaRDI QIDQ1603512

Qi Cheng, Fang Fang

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityRegular graphCombinatorial problemsGraph automorphism

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (1)

Regular induced subgraphs of a random Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic enumeration by degree sequence of graphs of high degree
• Kolmogorov Random Graphs and the Incompressibility Method
• Asymmetric graphs

This page was built for publication: Kolmogorov random graphs only have trivial stable colorings.