Thesis (M.S.)--Ohio University, March, 2004. / Title from PDF t.p. Includes bibliographical references (leaves 51-55).

Thesis (Ph. D.)--Auburn University, 2008. / Abstract. Includes bibliographical references (p. 77-78).

Thesis--Auburn University, 2009. / Abstract. Vita. Includes bibliographical references (p. 21).

A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.

M.Sc. / Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable.

abstract: The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum number of colors needed to color $V(G)$ such that no adjacent vertices receive the same color. The coloring number $\col(G)$ of a graph $G$ is the minimum number $k$ such that there exists a linear ordering of $V(G)$ for which each vertex has at most $k-1$ backward neighbors. It is well known that the coloring number is an upper bound for the chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is a generalization of the coloring number, and it was first introduced by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$ is the minimum integer $k$ such that for some linear ordering $L$ of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller vertices $u$ (with respect to $L$) with a path of length at most $r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$. The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$ is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$ if and only if the distance between $x$ and $y$ in $G$ is $3$. This dissertation improves the best known upper bound of the chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$ of planar graphs $G$, which is $105$, to $95$. It also improves the best known lower bound, which is $7$, to $9$. A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

No description available.

No description available.

No description available.

A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.