Informatics
Interval non-total colorable graphs
[Интервально тотально нераскрашиваемые графы]
N. A. Khachatryan Yerevan State University
Аннотация:
Тотальной раскраской графа
$G$ назовем такую раскраску вершин и ребер графа
$G$, при которой смежные вершины, смежные ребра и вершины, инцидентные ребрам, окрашены в различные цвета. Интервальной тотальной
$t$-раскраской графа
$G$ назовем тотальную раскраску графа
$G$ в цвета
$1,2,\dots,t$, при которой все цвета использованы и ребра, инцидентные каждой вершине
$v$, вместе с
$v$ окрашены в
$d_G(v)+1$ последовательных цветов, где
$d_G(v)$– степень вершины
$v$ в графе
$G$. В настоящей работе описываются некоторые методы построения графов, не обладающих интервальной тотальной раскраской.
Ключевые слова:
total coloring, interval total coloring, interval coloring.
MSC: 05C15 Поступила в редакцию: 23.04.2015
Принята в печать: 18.05.2015
Язык публикации: английский