If $G$ is a connected graph of order $n\ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in V\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);z\in V\left(G\right)\left)\right),$$ where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n\ge 3$. Assume that there exists a subgraph...

An incidence in a graph G is a pair (v, e) with v ∈ V (G) and e ∈ E(G), such that v and e are incident. Two incidences (v, e) and (w, f) are adjacent if v = w, or e = f, or the edge vw equals e or f. The incidence chromatic number of G is the smallest k for which there exists a mapping from the set of incidences of G to a set of k colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid Tm,n = Cm2Cn equals 5 when...

For a nontrivial connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. Detour distance is a metric on the vertex set of $G$. For each integer $k$ with $1\le k\le n-1$, a coloring $c:V\left(G\right)\to \mathbb{N}$ is a $k$-metric coloring of $G$ if $\left|c\right(u)-c(v\left)\right|+D(u,v)\ge k+1$ for every two distinct vertices $u$ and $v$ of $G$. The value ${\chi }_m^k\left(c\right)$ of a $k$-metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$-metric chromatic number ${\chi }_m^k\left(G\right)$ of $G$ is the minimum value of a $k$-metric coloring of $G$. For every...

Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF...

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 ${\chi }_m\left(G\right)$ of $G$. For every graph $G$, ${\chi }_m\left(G\right)$ is bounded above by its chromatic number $\chi \left(G\right)$. 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\ge 3$, there exist sufficiently...

Let ω(G) and χ(G) be the clique number and the chromatic number of a graph G. Mycielski [11] presented a construction that for any n creates a graph Mn which is triangle-free (ω(G) = 2) with χ(G) > n. The starting point is the complete graph of two vertices (K2). M(n+1) is obtained from Mn through the operation μ(G) called the Mycielskian of a graph G.We first define the operation μ(G) and then show that ω(μ(G)) = ω(G) and χ(μ(G)) = χ(G) + 1. This is done for arbitrary graph G, see also [10]....

Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_i$ has property ${}_i$. If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

For a nontrivial connected graph G, let c: V(G)→ N 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) ≠ 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 χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs are determined...

Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to 1,2,...,k such that vertices with color i have pairwise distance greater than $a_i$, and the S-packing chromatic number ${\chi }_S\left(G\right)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on...

If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is...