#### Date on Master's Thesis/Doctoral Dissertation

12-2012

#### Document Type

Doctoral Dissertation

#### Degree Name

Ph. D.

#### Department

Mathematics

#### Committee Chair

Kubicka, Ewa M.

#### Author's Keywords

Total coloring; graph theory; total independence number; chromatic sum

#### Subject

Graph theory; Map-coloring problem

#### Abstract

The area of total coloring is a more recent and less studied area than vertex and edge coloring, but recently, some attention has been given to the Total Coloring Conjecture, which states that each graph's total chromatic number xT is no greater than its maximum degree plus two. In this dissertation, it is proved that the conjecture is satisfied by those planar graphs in which no vertex of degree 5 or 6 1ies on more than three 3-cycles. The total independence number aT is found for some families of graphs, and a relationship between that parameter and the size of a graph's minimum maximal matching is discussed. For colorings with natural numbers, the total chromatic sum ST is introduced, as is total strength (oT of a graph. Tools are developed for proving that a total coloring has minimum sum, and this sum is found for some graphs including paths, cycles, complete graphs, complete bipartite graphs, full binary trees, and some hypercubes. A family of graphs is found for which no optimal total coloring maximizes the smallest color class. Lastly, the relationship between a graph's total chromatic number and its total strength is explored, and some graphs are found that require more than their total chromatic number of colors to obtain a minimum sum.

#### Recommended Citation

Leidner, Maxfield Edwin, "A study of the total coloring of graphs." (2012). *Electronic Theses and Dissertations.* Paper 815.

http://dx.doi.org/10.18297/etd/815