“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2335 |
|
| Abstract: | |
|
In this paper we investigate two conjectures proposed in (Graphs
Combin. 13(1997) 305-314. The first one is uniquely totally
colorable(UTC) conjecture which states: Empty graphs, paths, and
cycles of order 3k, k a natural number, are the only UTC
graphs. We show that if G is a UTC graph of order n, then
∆ ≤ n / 2 + 1, where ∆ is the maximum
degree of G. Also there is another question about UTC graphs
that appeared in (Graphs Combin. 13 (1997) 305-314) as follows: If
a graph G is UTC, is it true that in the proper total coloring
of G, each color is used for at least one vertax? We prove that
if G is a UTC graph of order n and in the proper total
coloring of G, there exists a color which did not appear in any
vertex of G, then G is a ∆-regular graph and n/2 ≤ ∆ ≤ n/2 + 1.
Download TeX format |
|
| back to top | |
