Edge colorings and total colorings of integer distance graphs

Arnfried Kemnitz; Massimiliano Marangio

The search session has expired. Please query the service again.

Displaying similar documents to “Edge colorings and total colorings of integer distance graphs”

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

A note on the chromatic number of the alternative negation of two graphs

Alejandro A. Schäffer, Ashok Subramanian (1988)

Colloquium Mathematicae

Similarity:

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Precoloring extension. II. Graphs classes related to bipartite graphs.

Hujter, M., Tuza, Zs. (1993)

Acta Mathematica Universitatis Comenianae. New Series

Similarity:

Clique-width and the speed of hereditary properties.

Allen, Peter, Lozin, Vadim, Rao, Michaël (2009)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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.

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.

On multiset colorings of graphs

Futaba Okamoto, Ebrahim Salehi, Ping Zhang (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset...

The chromatic sum of a graph: history and recent developments.

Kubicka, Ewa (2004)

International Journal of Mathematics and Mathematical Sciences

Similarity:

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

All Ramsey numbers $r (K_{3}, G)$ for connected graphs of order 9.

Brandt, Stephan, Brinkmann, Gunnar, Harmuth, Thomas (1998)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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

Graphs having planar complementary line (total) graphs.

Simic, Slobodan K. (1981)

Publications de l'Institut Mathématique. Nouvelle Série

Similarity: