Recognizable colorings of graphs

Gary Chartrand; Linda Lesniak; Donald W. VanderJagt; Ping Zhang

Displaying similar documents to “Recognizable colorings of graphs”

The multiset chromatic number of a graph

Gary Chartrand, Futaba Okamoto, Ebrahim Salehi, Ping Zhang (2009)

Mathematica Bohemica

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 $χ_{m} (G)$ of $G$ . For every graph $G$ , $χ_{m} (G)$ is bounded above by its chromatic number $χ (G)$ . The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each $k \geq 3$ , there...

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

Recognizable colorings of cycles and trees

Michael J. Dorfling, Samantha Dorfling (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and a vertex-coloring c:V(G) → 1,2, ...,k, the color code of a vertex v is the (k+1)-tuple (a₀,a₁, ...,aₖ), where a₀ = c(v), and for 1 ≤ i ≤ k, $a_{i}$ is the number of neighbors of v colored i. A recognizable coloring is a coloring such that distinct vertices have distinct color codes. The recognition number of a graph is the minimum k for which G has a recognizable k-coloring. In this paper we prove three conjectures of Chartrand et al. in [8] regarding the recognition number...

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