Displaying similar documents to “Sparse graphs usually have exponentially many optimal colorings.”

Ramsey Properties of Random Graphs and Folkman Numbers

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies...

The Chromatic Number of Random Intersection Graphs

Katarzyna Rybarczyk (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.

On 1-dependent ramsey numbers for graphs

E.J. Cockayne, C.M. Mynhardt (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively);...

Equitable coloring of Kneser graphs

Robert Fidytek, Hanna Furmańczyk, Paweł Żyliński (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k)...

Optimal Backbone Coloring of Split Graphs with Matching Backbones

Krzysztof Turowski (2015)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.