The multiset chromatic number of a graph

Gary Chartrand; Futaba Okamoto; Ebrahim Salehi; Ping Zhang

Displaying similar documents to “The multiset chromatic number of a graph”

Recognizable colorings of graphs

Gary Chartrand, Linda Lesniak, Donald W. VanderJagt, Ping Zhang (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and let c:V(G) → 1,2,...,k be a coloring of the vertices of G for some positive integer k (where adjacent vertices may be colored the same). The color code of a vertex v of G (with respect to c) is the ordered (k+1)-tuple code(v) = (a₀,a₁,...,aₖ) where a₀ is the color assigned to v and for 1 ≤ i ≤ k, $a_{i}$ is the number of vertices adjacent to v that are colored i. The coloring c is called recognizable if distinct vertices have distinct color codes and the recognition...

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

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

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

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