Displaying similar documents to “The chromatic sum of a graph: history and recent developments.”

Equitable Colorings Of Corona Multiproducts Of Graphs

Hanna Furmánczyk, Marek Kubale, Vahan V. Mkrtchyan (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts...

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)...

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Edge colorings and total colorings of integer distance graphs

Arnfried Kemnitz, Massimiliano Marangio (2002)

Discussiones Mathematicae Graph Theory

Similarity:

An integer distance graph is a graph G(D) with the set Z of integers as vertex set and two vertices u,v ∈ Z are adjacent if and only if |u-v| ∈ D where the distance set D is a subset of the positive integers N. In this note we determine the chromatic index, the choice index, the total chromatic number and the total choice number of all integer distance graphs, and the choice number of special integer distance graphs.

k -Ramsey classes and dimensions of graphs

Jan Kratochvíl (1995)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In this note, we introduce the notion of k -Ramsey classes of graphs and we reveal connections to intersection dimensions of graphs.

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Oleg V. Borodin, Anna O. Ivanova (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

List coloring of complete multipartite graphs

Tomáš Vetrík (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.

Grundy number of graphs

Brice Effantin, Hamamache Kheddouci (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally,...