Displaying similar documents to “Constructive lower bounds on classical multicolor Ramsey numbers.”

Bounds for the b-Chromatic Number of Subgraphs and Edge-Deleted Subgraphs

P. Francis, S. Francis Raj (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we obtain bounds for the b- chromatic number of induced subgraphs in terms of the b-chromatic number of the original graph. This turns out to be...

The upper domination Ramsey number u(4,4)

Tomasz Dzido, Renata Zakrzewska (2006)

Discussiones Mathematicae Graph Theory

Similarity:

The upper domination Ramsey number u(m,n) is the smallest integer p such that every 2-coloring of the edges of Kₚ with color red and blue, Γ(B) ≥ m or Γ(R) ≥ n, where B and R is the subgraph of Kₚ induced by blue and red edges, respectively; Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. In this paper, we show that u(4,4) ≤ 15.

The set chromatic number of a graph

Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)

Discussiones Mathematicae Graph Theory

Similarity:

For a nontrivial connected graph G, let c: V(G)→ N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u,v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs...

Almost-Rainbow Edge-Colorings of Some Small Subgraphs

Elliot Krop, Irina Krop (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let f(n, p, q) be the minimum number of colors necessary to color the edges of Kn so that every Kp is at least q-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] and for all even n ≢ 1(mod 3), f(n, 4, 5) ≤ n− 1. For a complete bipartite graph G= Kn,n, we show an n-color construction to color...

A Note on Neighbor Expanded Sum Distinguishing Index

Evelyne Flandrin, Hao Li, Antoni Marczyk, Jean-François Saclé, Mariusz Woźniak (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Semi-definite positive programming relaxations for graph K 𝐧 -coloring in frequency assignment

Philippe Meurdesoif, Benoît Rottembourg (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n -uples of colors used to color a given set of n -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find...

Coloring with no 2-colored P 4 's.

Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)

The Electronic Journal of Combinatorics [electronic only]

Similarity: