# Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

Research paper by **Petros A. Petrosyan, Nerses A. Khachatryan**

Indexed on: **11 Aug '14**Published on: **11 Aug '14**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

A total coloring of a graph $G$ is a coloring of its vertices and edges such
that no adjacent vertices, edges, and no incident vertices and edges obtain the
same color. An interval total $t$-coloring of a graph $G$ is a total coloring
of $G$ with colors $1,\ldots,t$ such that all colors are used, and the edges
incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$
consecutive colors, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. In
this paper we prove that all complete multipartite graphs with the same number
of vertices in each part are interval total colorable. Moreover, we also give
some bounds for the minimum and the maximum span in interval total colorings of
these graphs. Next, we investigate interval total colorings of hypercubes
$Q_{n}$. In particular, we prove that $Q_{n}$ ($n\geq 3$) has an interval total
$t$-coloring if and only if $n+1\leq t\leq \frac{(n+1)(n+2)}{2}$.