You are here
Hadwiger Numbers and GallaiRamsey Numbers of Special Graphs
 Date Issued:
 2019
 Abstract/Description:
 This dissertation explores two separate topics on graphs.We first study a farreaching 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's 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's 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 Gallaicolorings. A Gallaicoloring of a complete graph is an edgecoloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the GallaiRamsey number, denoted GR_k(H), is the least positive integer n such that every Gallaicoloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more wellbehaved 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.
Title:  Hadwiger Numbers and GallaiRamsey Numbers of Special Graphs. 
19 views
10 downloads 

Name(s): 
Bosse, Christian, Author Song, Zixia, Committee Chair Brennan, Joseph, Committee Member Zhao, Yue, Committee Member DeMara, Ronald, Committee Member University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2019  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  This dissertation explores two separate topics on graphs.We first study a farreaching 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's 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's 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 Gallaicolorings. A Gallaicoloring of a complete graph is an edgecoloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the GallaiRamsey number, denoted GR_k(H), is the least positive integer n such that every Gallaicoloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more wellbehaved 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.  
Identifier:  CFE0007603 (IID), ucf:52532 (fedora)  
Note(s): 
20190801 Ph.D. Sciences, Mathematics Doctoral This record was generated from author submitted information. 

Subject(s):  Hadwiger number  Graph minor  W5free  Gallaicoloring  GallaiRamsey number  rainbow triangle  
Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0007603  
Restrictions on Access:  public 20190815  
Host Institution:  UCF 