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,... ,t such that all colors are used, and the edges incident to each vertex v together with v are colored by dG (v) + 1 consecutive colors, where dG(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 Qn. In particular, we prove that Qn (n≥ 3) has an interval total t-coloring if and only if n + 1 ≤ t ≤ ( (n+1Xn+2)/2) .
; Тотальной раскраской графа G назовем такую раскраску вершин и ребер графа G, при которой смежные вершины, смежные ребра и вершины, инцидентные ребрам, окрашены в различные цвета. Интервальной тотальной t— раскраской графа G назовем тотальную раскраску графа G в цвета 1, . . . ,t при которой все цвета использованы, и ребра, инцидентные каждой вершине v вместе с v, окрашены в dG(v) + 1 последовательных цветов, где dG(v) - это степень вершины v в графе G. В настоящей работе доказано, что все полные многодольные графы с одинаковым количеством вершин в каждой доле имеют интервальную тотальную раскраску. Кроме того, получены некоторые оценки наименьшего и наибольшего возможного числа цветов в интервальных тотальных раскрасках этих графов. В работе также исследованы интервальные тотальные раскраски гиперкубов Qn. В частности, доказано, что гиперкуб Qn (n ≥ 3 ) имеет интервальную тотальную раскраску тогда и только тогда, когда n + 1 ≤ t ≤ ( (n+1Xn+2)/2) .

Date submitted:

05.08.2014

Date accepted:

27.11.2014

Identifier:

oai:noad.sci.am:135977

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

42

URL:

Additional Information:

pet_petros@ipia.sci.am ; xachnerses@gmail.com

Affiliation:

Institute for Informatics and Automation Problems ; Department of Informatics and Applied Mathematics, YSU

Country:

Armenia

Indexing:

ASCI