RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, Physical and Mathematical Sciences, 2015 Issue 3, Pages 37–41 (Mi uzeru34)

Informatics

Interval non-total colorable graphs

N. A. Khachatryan

Yerevan State University

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,2,\dots,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 describe some methods for constructing of graphs that have no interval total coloring.

Keywords: total coloring, interval total coloring, interval coloring.

MSC: 05C15

Received: 23.04.2015
Accepted: 18.05.2015

Language: English



© Steklov Math. Inst. of RAS, 2024