Distance coloring of the hexagonal lattice

Peter Jacko; Stanislav Jendrol'

Displaying similar documents to “Distance coloring of the hexagonal lattice”

3-consecutive c-colorings of graphs

Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, M.S. Subramanya, Charles Dominic (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ${(χ ̅)}_{3 C C} (G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ${(χ ̅)}_{3 C C} (G) \geq k$ for k = 3 and k = 4.

Radio k-colorings of paths

Gary Chartrand, Ladislav Nebeský, Ping Zhang (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings...

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_{v}$ for the vertices v ∈ V are given, and the question...

Fall coloring of graphs I

Rangaswami Balakrishnan, T. Kavaskar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A fall coloring of a graph G is a proper coloring of the vertex set of G such that every vertex of G is a color dominating vertex in G (that is, it has at least one neighbor in each of the other color classes). The fall coloring number $χ_{f} (G)$ of G is the minimum size of a fall color partition of G (when it exists). Trivially, for any graph G, $χ (G) \leq χ_{f} (G)$ . In this paper, we show the existence of an infinite family of graphs G with prescribed values for χ(G) and $χ_{f} (G)$ . We also obtain the smallest non-fall...

Upper bounds on the b-chromatic number and results for restricted graph classes

Mais Alkhateeb, Anja Kohl (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number $χ_{b} (G)$ is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying $χ (G) \leq k \leq χ_{b} (G)$ . In this paper, we establish four general upper bounds on $χ_{b} (G)$ . We present results on the b-chromatic...

On the special context of independent sets

Vladimír Slezák (2001)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

In this paper the context of independent sets $J_{L}^{p}$ is assigned to the complete lattice (P(M),⊆) of all subsets of a non-empty set M. Some properties of this context, especially the irreducibility and the span, are investigated.

Every lattice is embeddable in the lattice of $T_{1}$ -topologies

Richard Valent (1973)

Colloquium Mathematicae

Similarity:

Maximum Edge-Colorings Of Graphs

Stanislav Jendrol’, Michaela Vrbjarová (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $χ_{r}^{'} (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $χ_{r}^{'} (G) \leq 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i...

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k + 1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang (2002)

Mathematica Bohemica

Similarity:

A radio antipodal coloring of a connected graph $G$ with diameter $d$ is an assignment of positive integers to the vertices of $G$ , with $x \in V (G)$ assigned $c (x)$ , such that $d (u, v) + | c (u) - c (v) | \geq d$ for every two distinct vertices $u$ , $v$ of $G$ , where $d (u, v)$ is the distance between $u$ and $v$ in $G$ . The radio antipodal coloring number $a c (c)$ of a radio antipodal coloring $c$ of $G$ is the maximum color assigned to a vertex of $G$ . The radio antipodal chromatic number $a c (G)$ of $G$ is $min {a c (c)}$ over all radio antipodal colorings $c$ of $G$ . Radio antipodal chromatic numbers...

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers $s_{i}$ and $t_{i}$ satisfying $1 \leq s_{i} \leq t_{i} \leq | E_{i} |$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_{i}$ satisfies $s_{i} \leq | φ (E_{i}) | \leq t_{i}$ . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each $E_{i}$ induces a connected subgraph in G....

Localization of jumps of the point-distinguishing chromatic index of $K_{n, n}$

Mirko Horňák, Roman Soták (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of $K_{n, n}$ is found.

Two variants of the size Ramsey number

Andrzej Kurek, Andrzej Ruciński (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m (G) = m a x_{F \subseteq G} | E (F) | / | V (F) |$ and define the Ramsey density $m_{i n f} (H, r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{i n f} (H, r) = (R - 1) / 2$ , where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited...

The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami, Lutz Volkmann (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set 1,2, ...,k such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃u ∈ N(v)f(u) = 1,2, ...,k is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set $f ₁, f ₂, . . ., f_{d}$ of k-rainbow dominating functions on G with the property that $\sum_{i = 1}^{d} | f_{i} (v) | \leq k$ for each v ∈ V(G), is called a k-rainbow dominating...

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang (2008)

Mathematica Bohemica

Similarity:

Let $G$ be a nontrivial connected graph on which is defined a coloring $c E (G) \to {1, 2, ..., k}$ , $k \in ℕ$ , of the edges of $G$ , where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ contains a rainbow $u - v$ path for every two vertices $u$ and $v$ of $G$ . The minimum $k$ for which there exists such a $k$ -edge coloring is the rainbow connection number $r c (G)$ of $G$ . If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u - v$ geodesic,...