“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2335
School of Mathematics
  Title:   Two conjectures on uniquely totally colorable graphs
  Author(s):  S. Akbari
  Status:   Published
  Journal: Discrete Math.
  Vol.:  266
  Year:  2003
  Pages:   41-45
  Supported by:  IPM
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
scroll left or right