Radio k-colorings of paths

Gary Chartrand; Ladislav Nebeský; Ping Zhang

Displaying similar documents to “Radio k-colorings of paths”

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

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

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

Multicolor Ramsey numbers for paths and cycles

Tomasz Dzido (2005)

Discussiones Mathematicae Graph Theory

Similarity:

For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some $G_{i}$ , for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices,...

Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph

D. Ali Mojdeh (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G =...

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

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

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.

Kaleidoscopic Colorings of Graphs

Gary Chartrand, Sean English, Ping Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . . , k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular...

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

Set vertex colorings and joins of graphs

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

Czechoslovak Mathematical Journal

Similarity:

For a nontrivial connected graph $G$ , let $c V (G) \to ℕ$ 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) \neq 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 $χ_{s} (G)$ . A study is made of the set chromatic number of the join $G + H$ of two graphs $G$ and $H$ . Sharp lower...