On total chromatic number of direct product graphs |
| |
Authors: | Katja Prnaver Blaž Zmazek |
| |
Affiliation: | 1. Institute for Mathematics, Physics and Mechanics, Jadranska 19, 1000, Ljubljana, Slovenia 2. Faculty of Mathematics and Natural Sciences, University of Maribor, Koro?ka c. 160, 2000, Maribor, Slovenia
|
| |
Abstract: | Coloring of the graph products, especially vertex and edge coloring, has been widely researched for all types of graph products. For total graph coloring, as combination of edge and vertex coloring, Behzad and Vizing set Total Coloring Conjecture in mid 1960s. In this paper, we prove the conjecture for two specific direct graph products, for direct product of path and arbitrary graph G, P n ×G, where χ′(G)=Δ(G), and expand the proof onto direct product of arbitrary cycle and a path P n , C m ×P n . At the same time, the proofs provide the algorithms to color such graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|