Current Search: Reid, Michael (x)
View All Items
 Title
 Tiling with Polyominoes, Polycubes, and Rectangles.
 Creator

Saxton, Michael, Reid, Michael, Lee, Junho, Han, Deguang, University of Central Florida
 Abstract / Description

In this paper we study the hierarchical structure of the 2d polyominoes. We introduce a new infinite family of polyominoes which we prove tiles a strip. We discuss applications of algebra to tiling. We discuss the algorithmic decidability of tiling the infinite plane Z x Z given a finite set of polyominoes. We will then discuss tiling with rectangles. We will then get some new, and some analogous results concerning the possible hierarchical structure for the 3d polycubes.
 Date Issued
 2015
 Identifier
 CFE0005995, ucf:50791
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0005995
 Title
 Interval EdgeColorings of Graphs.
 Creator

Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
 Abstract / Description

A proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so...
Show moreA proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edgecoloring.A wellknown result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edgechromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edgecoloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edgecoloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edgecoloring is NPcomplete. In this thesis, we survey known results on interval edgecolorings of graphs, with a focus on the progress of $(a, b)$biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.
Show less  Date Issued
 2016
 Identifier
 CFE0006301, ucf:51609
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006301
 Title
 Coloring graphs with forbidden minors.
 Creator

Rolek, Martin, Song, Zixia, Brennan, Joseph, Reid, Michael, Zhao, Yue, DeMara, Ronald, University of Central Florida
 Abstract / Description

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Ktminor is (t  1)colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in...
Show moreA graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Ktminor is (t  1)colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in the process giving a shorter and computerfree proof of the known results for t = 7, 8. We also show that this result extends to larger values of t if Mader's bound for the extremal function for Ktminors is true. Additionally, we show that any graph with no K8?minor is 9colorable, and any graph with no K8?minor is 8colorable. The Kempechain method developed for our proofs of the above results may be of independent interest. We also use Mader's HWege theorem to establish some sufficient conditions for a graph to contain a K8minor.Another motivation for my research is a wellknown conjecture of Erd?s and Lov(&)#225;sz from 1968, the DoubleCritical Graph Conjecture. A connected graph G is doublecritical if for all edges xy ? E(G), ?(G  x  y) = ?(G)  2. Erd?s and Lov(&)#225;sz conjectured that the only doublecritical tchromatic graph is the complete graph Kt. This conjecture has been show to be true for t ? 5 and remains open for t ? 6. It has further been shown that any noncomplete, doublecritical, tchromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computerfree proof for t = 8, and extend the result to show that G contains a K9minor for all t ? 9. Finally, we show that the DoubleCritical Graph Conjecture is true for doublecritical graphs with chromatic number t ? 8 if such graphs are clawfree.
Show less  Date Issued
 2017
 Identifier
 CFE0006649, ucf:51227
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006649