Kolmogorov random graphs only have trivial stable colorings

Authors
Citation
Q. Cheng et F. Fang, Kolmogorov random graphs only have trivial stable colorings, INF PROCESS, 81(3), 2002, pp. 133-136
Citations number
7
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
0020-0190 → ACNP
Volume
81
Issue
3
Year of publication
2002
Pages
133 - 136
Database
ISI
SICI code
0020-0190(20020214)81:3<133:KRGOHT>2.0.ZU;2-7
Abstract
In this paper, we prove that random graphs only have trivial stable colorin gs. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundation s of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective versi on of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a bypro duct, we also give an upper bound of the size of induced regular subgraphs in random graphs. (C) 2002 Elsevier Science B.V. All rights reserved.