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.

Download

Share

COinS