Files in this item
Files  Description  Format 

application/pdf REINIGERDISSERTATION2015.pdf (539kB)  (no description provided) 
Description
Title:  Coloring and constructing (hyper)graphs with restrictions 
Author(s):  Reiniger, Benjamin M 
Director of Research:  Kostochka, Alexandr V. 
Doctoral Committee Chair(s):  West, Douglas B. 
Doctoral Committee Member(s):  Reznick, Bruce A.; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graph coloring
hypergraph coloring critical graphs list coloring hypergraph degrees poset dimension 
Abstract:  We consider questions regarding the existence of graphs and hypergraphs with certain coloring properties and other structural properties. In Chapter 2 we consider colorcritical graphs that are nearly bipartite and have few edges. We prove a conjecture of Chen, Erdős, Gyárfás, and Schelp concerning the minimum number of edges in a “nearly bipartite” 4critical graph. In Chapter 3 we consider coloring and listcoloring graphs and hypergraphs with few edges and no small cycles. We prove two main results. If a bipartite graph has maximum average degree at most 2(k−1), then it is colorable from lists of size k; we prove that this is sharp, even with an additional girth requirement. Using the same approach, we also provide a simple construction of graphs with arbitrarily large girth and chromatic number (first proved to exist by Erdős). In Chapter 4 we consider listcoloring the family of kth power graphs. Kostochka and Woodall conjectured that graph squares are chromaticchoosable, as a strengthening of the Total List Coloring Conjecture. Kim and Park disproved this stronger conjecture, and Zhu asked whether graph kth powers are chromaticchoosable for any k. We show that this is not true: we construct families of graphs based on affine planes whose choice number exceeds their chromatic number by a logarithmic factor. In Chapter 5 we consider the existence of uniform hypergraphs with prescribed degrees and codegrees. In Section 5.2, we show that a generalization of the graphic 2switch is insufficient to connect realizations of a given degree sequence. In Section 5.3, we consider an operation on 3graphs related to the octahedron that preserves codegrees; this leads to an inductive definition for 2colorable triangulations of the sphere. In Section 5.4, we discuss the notion of fractional realizations of degree sequences, in particular noting the equivalence of the existence of a realization and the existence of a fractional realization in the graph and multihypergraph cases. In Chapter 6 we consider a question concerning poset dimension. Dorais asked for the maximum guaranteed size of a subposet with dimension at most d of an nelement poset. A lower bound of sqrt(dn) was observed by Goodwillie. We provide a sublinear upper bound. 
Issue Date:  20150706 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/87975 
Rights Information:  Copyright 2015 Benjamin M. Reiniger 
Date Available in IDEALS:  20150929 
Date Deposited:  August 201 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois