Sparse graphs usually have exponentially many optimal colorings
type: Item
instance of: scholarly article
title: Sparse graphs usually have exponentially many optimal colorings
zbMATH Open document ID: 0989.05106
author: Michael Krivelevich
published in: The Electronic Journal of Combinatorics
publication date: 2002-07-01T00:00:00Z
full work available at URL: https://eudml.org/doc/121889
full work available at URL: v9i1r27.html
review text: Summary: A proper coloring of a graph \(G=(V,E)\) is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of \(G\). We investigate the typical behavior of the number of distinct optimal colorings of a random graph \(G(n,p)\), for various values of the edge probability \(p=p(n)\). Our main result shows that for every constant \(1/3<a<2\), most of the graphs in the probability space \(G(n,p)\) with \(p=n^{-a}\) have exponentially many optimal colorings.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1757093
zbMATH Keywords: chromatic number
zbMATH Keywords: random graph
zbMATH Keywords: optimal colorings
MaRDI profile type: MaRDI publication profile
Recommended article: Q3749092
Recommended article: Q5187324
Recommended article: Randomly coloring sparse random graphs with fewer colors than the maximum degree
Recommended article: On the chromatic number of random graphs
Recommended article: The Choice Number of Dense Random Graphs
description: scientific article; zbMATH DE number 1757093