Chromatic Polynomials for Graphs with Split Vertices

Download or read book Chromatic Polynomials for Graphs with Split Vertices written by Sarah E. Adams and published by . This book was released on 2020 with total page 49 pages. Available in PDF, EPUB and Kindle. Book excerpt: Graph theory is a branch of mathematics that uses graphs as a mathematical structure to model relations between objects. Graphs can be categorized in a wide variety of graph families. One important instrument to classify graphs is the chromatic polynomial. This was introduced by Birkhoff in 1912 and allowed to further study and develop several graph related problems. In this thesis, we study some problems that can be approached using the chromatic polynomial. In the first chapter, we introduce general definitions and examples of graphs. In the second chapter, we talk about graph colorings, the greedy algorithm, and give a short description for the four color problem. In the third chapter, we introduce the chromatic polynomial, study its property, and give some examples of computations. All of these are classical results. In chapter 4, we introduce colorings of graphs with split vertices, and give an application to the scheduling problem. Also, we show how the chromatic polynomial can be used in that setting. This is our "semi-original" contribution. Finally, in the last chapter, we talk about distance two colorings for graphs, and give examples on how this applies to coloring maps.