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

D. Ali Mojdeh

Displaying similar documents to “Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph”

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

A new upper bound for the chromatic number of a graph

Ingo Schiermeyer (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n with clique number ω(G), chromatic number χ(G) and independence number α(G). We show that χ(G) ≤ [(n+ω+1-α)/2]. Moreover, χ(G) ≤ [(n+ω-α)/2], if either ω + α = n + 1 and G is not a split graph or α + ω = n - 1 and G contains no induced $K_{ω + 3} - C ₅$ .

On the dominator colorings in trees

Houcine Boumediene Merouane, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates...

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

On detectable colorings of graphs

Henry Escuadro, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

Let $G$ be a connected graph of order $n \geq 3$ and let $c E (G) \to {1, 2, ..., k}$ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$ , the color code of $v$ with respect to $c$ is the $k$ -tuple $c (v) = (a_{1}, a_{2}, \dots, a_{k})$ , where $a_{i}$ is the number of edges incident with $v$ that are colored $i$ ( $1 \leq i \leq k$ ). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$ -coloring. We establish a formula for the...

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

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

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

On stratification and domination in graphs

Ralucca Gera, Ping Zhang (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number $γ_{F} (G)$ is the minimum number of red vertices in an F-coloring...