For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power $D^k$ of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of $D^k$ if the directed distance ${}^{\to }{d}_D(u,v)$ from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph $D^k$ is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph $D^k$ is distance-colored if each arc (u, v) of $D^k$ is assigned the color i where $i{=}^{\to }{d}_D(u,v)$. The digraph $D^k$ is Hamiltonian-colored...

The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper...

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring...

By means of branched coverings techniques, we prove that the Heegaard genus and the regular genus of an orientable 3-manifold with boundary coincide.

A 2-stratified graph $G$ is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of $G$. Two $2$-stratified graphs $G$ and $H$ are isomorphic if there exists a color-preserving isomorphism $\phi$ from $G$ to $H$. A $2$-stratified graph $G$ is said to be homogeneously embedded in a $2$-stratified graph $H$ if for every vertex $x$ of $G$ and every vertex $y$ of $H$, where $x$ and $y$ are colored the same, there exists an induced $2$-stratified subgraph $H^{\text{'}}$ of $H$ containing $y$ and a color-preserving...

In this note it is shown that every hypergraph containing a pendant path of length at least 2 is not chromatically unique. The same conclusion holds for h-uniform r-quasi linear 3-cycle if r ≥ 2.

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+2$ for every positive integer n, where ac’(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-n/2-⎣10/n⎦+7$ if n is even positive integer and n ≥ 10, and $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-(n-1)/2-⎣13/n⎦+8$ if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

In this paper, we construct infinite families of tight regular tournaments. In particular, we prove that two classes of regular tournaments, tame molds and ample tournaments are tight. We exhibit an infinite family of 3-dichromatic tight tournaments. With this family we positively answer to one case of a conjecture posed by V. Neumann-Lara. Finally, we show that any tournament with a tight mold is also tight.

In this paper, we consider the intersection graph $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{\Gamma }\left(\mathbb{Z}ₙ\right)$.