Displaying similar documents to “Unit distance graphs with ambiguous chromatic number.”

Coloring Some Finite Sets in ℝn

József Balogh, Alexandr Kostochka, Andrei Raigorodskii (2013)

Discussiones Mathematicae Graph Theory

Similarity:

This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in...

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.

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

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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

Sum List Edge Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f)...

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Csilla Bujtás, Zsolt Tuza (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM...

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

4-chromatic Koester graphs

Andrey A. Dobrynin, Leonid S. Mel'nikov (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples...

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.

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

On (p, 1)-total labelling of 1-planar graphs

Xin Zhang, Yong Yu, Guizhen Liu (2011)

Open Mathematics

Similarity:

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.