Current Search:   Reid, Michael (x)

View All Items

  • CSV Spreadsheet
(1 - 3 of 3)
Tiling with Polyominoes, Polycubes, and Rectangles
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 2-d 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 3-d polycubes.
Date Issued
2015
Identifier
CFE0005995, ucf:50791
Format
Document (PDF)
PURL
http://purl.flvc.org/ucf/fd/CFE0005995
Interval Edge-Colorings of Graphs
Title
Interval Edge-Colorings of Graphs.
Creator
Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
Abstract / Description
A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring 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 edge-colorings 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 edge-colorings to schedule parent-teacher conferences so...
Show moreA proper edge-coloring of a graph G by positive integers is called an interval edge-coloring 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 edge-colorings 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 edge-colorings to schedule parent-teacher 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 edge-coloring.A well-known result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edge-chromatic 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 edge-coloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edge-coloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edge-coloring is NP-complete. In this thesis, we survey known results on interval edge-colorings 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
Coloring graphs with forbidden minors
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 Kt-minor 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 K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor 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 Kt-minor 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 K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in the process giving a shorter and computer-free 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 Kt-minors is true. Additionally, we show that any graph with no K8?-minor is 9-colorable, and any graph with no K8?-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use Mader's H-Wege theorem to establish some sufficient conditions for a graph to contain a K8-minor.Another motivation for my research is a well-known conjecture of Erd?s and Lov(&)#225;sz from 1968, the Double-Critical Graph Conjecture. A connected graph G is double-critical if for all edges xy ? E(G), ?(G - x - y) = ?(G) - 2. Erd?s and Lov(&)#225;sz conjectured that the only double-critical t-chromatic 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 non-complete, double-critical, t-chromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computer-free proof for t = 8, and extend the result to show that G contains a K9-minor for all t ? 9. Finally, we show that the Double-Critical Graph Conjecture is true for double-critical graphs with chromatic number t ? 8 if such graphs are claw-free.
Show less
Date Issued
2017
Identifier
CFE0006649, ucf:51227
Format
Document (PDF)
PURL
http://purl.flvc.org/ucf/fd/CFE0006649