A note on the non-colorability threshold of a random graph
type: Item
instance of: scholarly article
title: A note on the non-colorability threshold of a random graph
zbMATH Open document ID: 0939.05073
author: L. M. Kirousis
author: Yannis C. Stamatiou
author: A. C. Kaporis
published in: The Electronic Journal of Combinatorics
publication date: 2000-06-07T00:00:00Z
full work available at URL: https://eudml.org/doc/120357
full work available at URL: v7i1r29.html
review text: Summary: In this paper we consider the problem of establishing a value \(r_0\) such that almost all random graphs with \(n\) vertices and \(rn\) edges, \(r > r_0\), are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by \textit{A. Kamath}, \textit{R. Motwani}, \textit{K. Palem}, and \textit{P. Spirakis} [Random Struct. Algorithms 7, No. 1, 59-80 (1995; Zbl 0834.68051)] of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value \(r_0 = 2.522\) previously obtained by \textit{D. Achlioptas} and \textit{M. Molloy} [Electron. J. Comb. 6, No. 1, Research paper 29, 9p. (1999; Zbl 0919.05056)] to \(r_0 = 2.495\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1456994
zbMATH Keywords: non-colorability
zbMATH Keywords: random graphs
zbMATH Keywords: colorings
zbMATH Keywords: occupancy problem
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1456994