Hadwiger Numbers and Gallai-Ramsey Numbers of Special Graphs

This dissertation explores two separate topics on graphs. We first study a far-reaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger\u27s conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is perhaps the most famous conjecture in Graph Theory and remains open even for graphs G with alpha(G) less than or equal to 2. Let W_5 denote the wheel on six vertices. We establish more evidence for Hadwiger\u27s conjecture by proving that h(G) is greater than or equal to chi(G) for all graphs G such that alpha(G) is less than or equal to 2 and G does not contain W_5 as an induced subgraph. Our second topic is related to Ramsey theory, a field that has intrigued those who study combinatorics for many decades. Computing the classical Ramsey numbers is a notoriously difficult problem, leaving many basic questions unanswered even after more than 80 years. We study Ramsey numbers under Gallai-colorings. A Gallai-coloring of a complete graph is an edge-coloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the Gallai-Ramsey number, denoted GR_k(H), is the least positive integer n such that every Gallai-coloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more well-behaved than the classical Ramsey number R_k(H), though finding exact values of GR_k(H) is far from trivial. We show that for all k at least 3, GR_k(C_{2n+1}) = n2^k+1 where n is 4, 5, 6 or 7, and GR_k(C_{2n+1}) is at most (n ln n)2^k-(k+1)n+1 for all n at least 8, where C_{2n+1} denotes a cycle on 2n+1 vertices