2026-09-21T12:20:20Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/92769 2023-07-11 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

This Dissertation was approved for publication on 2016-07-07 at 14:43. Kostochka, Alexandr V. Reznick, Bruce West, Douglas B. Molla, Theodore Santana, Michael L 2016-11-10T17:50:13Z 2016-11-10T17:50:13Z 2016-07-07 2016-08 In this Thesis, we consider two main themes: conditions that guarantee diverse cycle structure within a graph, and the existence of strong edge-colorings for a specific family of graphs. In Chapter 2 we consider a question closely related to the Matthews-Sumner conjecture, which states that every 4-connected claw-free graph is Hamiltonian. Since there exists an infinite family of 4-connected claw-free graphs that are not pancyclic, Gould posed the problem of characterizing the pairs of graphs, {X,Y}, such that every 4-connected {X,Y}-free graph is pancyclic. In this chapter we describe a family of pairs of graphs such that if every 4-connected {X,Y}-free graph is pancyclic, then {X,Y} is in this family. Furthermore, we show that every 4-connected {K_(1,3),N(4,1,1)}-free graph is pancyclic. This result, together with several others, completes a characterization of the family of subgraphs, F such that for all H in ∈, every 4-connected {K_(1,3), H}-free graph is pancyclic. In Chapters and 4 we consider refinements of results on cycles and chorded cycles. In 1963, Corrádi and Hajnal proved a conjecture of Erdös, showing that every graph G on at least 3k vertices with minimum degree at least 2k contains k disjoint cycles. This result was extended by Enomoto and Wang, who independently proved that graphs on at least 3kvertices with minimum degree-sum at least 4k - 1 also contain k disjoint cycles. Both results are best possible, and recently, Kierstead, Kostochka, Molla, and Yeager characterized their sharpness examples. A chorded cycle analogue to the result of Corrádi and Hajnal was proved by Finkel, and a similar analogue to the result of Enomoto and Wang was proved by Chiba, Fujita, Gao, and Li. In Chapter 3 we characterize the sharpness examples to these statements, which provides a chorded cycle analogue to the characterization of Kierstead et al. In Chapter 4 we consider another result of Chiba et al., which states that for all integers r and s with r + s ≥ 1, every graph G on at least 3r + 4s vertices with ẟ(G) ≥ 2r+3s contains r disjoint cycles and s disjoint chorded cycles. We provide a characterization of the sharpness examples to this result, which yields a transition between the characterization of Kierstead et al. and the main result of Chapter 3. In Chapter 5 we move to the topic of edge-colorings, considering a variation known as strong edge-coloring. In 1990, Faudree, Gyárfás, Schelp, and Tuza posed several conjectures regarding strong edge-colorings of subcubic graphs. In particular, they conjectured that every subcubic planar graph has a strong edge-coloring using at most nine colors. We prove a slightly stronger form of this conjecture, showing that it holds for all subcubic planar loopless multigraphs. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-11-09 without embargo terms The student, Michael Santana, accepted the attached license on 2016-07-07 at 10:58. The student, Michael Santana, submitted this Dissertation for approval on 2016-07-07 at 11:07. DSpace SAF Submission Ingestion Package generated from Vireo submission #9795 on 2016-11-09 at 10:23:00 Made available in DSpace on 2016-11-10T17:50:13Z (GMT). No. of bitstreams: 10 SANTANA-DISSERTATION-2016.pdf: 849992 bytes, checksum: 34f7fb6172faac629619f058f530460e (MD5) Abstract.tex: 3065 bytes, checksum: 9db5a41eb917b09880e823893333cf56 (MD5) Chorded.tex: 71076 bytes, checksum: e6ae208556ae875b312789f5b510354b (MD5) Dissertation.tex: 15780 bytes, checksum: 76175b03a7370b09bf7fe6cdb42ec6a5 (MD5) Mixed.tex: 123475 bytes, checksum: 588fa1d13182a59e642889777dfc466d (MD5) Overview.tex: 47740 bytes, checksum: be969796b5a27b8701a0af45b4412cf0 (MD5) Pancyclicity.tex: 104431 bytes, checksum: c74d6bd4b90779865c1dc7bfb8b5ce2b (MD5) Strong.tex: 104688 bytes, checksum: 2b86683993a7c4907a3c926022b7e30b (MD5) Symbols.tex: 1508 bytes, checksum: 97e802db00ecc2e66398c2eca338cf66 (MD5) LICENSE.txt: 4212 bytes, checksum: 22ab01b2ba3084b5321c9b77a1117c37 (MD5) Previous issue date: 2016-07-07 application/pdf http://hdl.handle.net/2142/92769 en Copyright 2016 Michael Santana graphs cycles strong edge-colorings Extremal problems on cycle structure and colorings of graphs text text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.