Extremal problems on cycle structure and colorings of graphs

graphs;cycles;strong edge-colorings

Santana, Michael L

关键词: graphs;    cycles;    strong edge-colorings;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/92769/SANTANA-DISSERTATION-2016.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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-connectedclaw-free graph is Hamiltonian.Since there exists an infinite family of 4-connectedclaw-free graphs that are not pancyclic, Gouldposed 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 Chaptersand 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.