Show simple item record

dc.contributor.authorHompe, Patrick
dc.date.accessioned2022-08-22 19:31:23 (GMT)
dc.date.available2022-08-22 19:31:23 (GMT)
dc.date.issued2022-08-22
dc.date.submitted2022-08-15
dc.identifier.urihttp://hdl.handle.net/10012/18605
dc.description.abstractWe show results in areas related to extremal problems in directed graphs. The first concerns a rainbow generalization of the Caccetta-H\"{a}ggkvist conjecture, made by Aharoni. The Caccetta-H\"{a}ggkvist conjecture states that if $G$ is a simple digraph on $n$ vertices with minimum out-degree at least $k$, then there exists a directed cycle in $G$ of length at most $\lceil n/k \rceil$. Aharoni proposed a generalization of this well-known conjecture, namely that if $G$ is a simple edge-colored graph (not necessarily properly colored) on $n$ vertices with $n$ color classes each of size at least $k$, then there exists a rainbow cycle in $G$ of length at most $\lceil n/k \rceil$. In this thesis, we first prove that if $G$ is an edge-colored graph on $n$ vertices with $n$ color classes each of size at least $\Omega(k \log{k})$, then $G$ has a rainbow cycle of length at most $\lceil n/k \rceil$. Then, we develop more techniques to prove the stronger result that if there are $n$ color classes, each of size at least $\Omega(k)$, then there is a rainbow cycle of length at most $\lceil n/k \rceil$. Finally, we improve upon existing bounds for the triangle case, showing that if there are $n$ color classes of size at least $0.3988n$, then there exists a rainbow triangle, and also if there are $1.1077n$ color classes of size at least $n/3$, then there is a rainbow triangle. Let $\chi(G)$ denote the \emph{chromatic number} of a graph $G$ and let $\omega(G)$ denote the \emph{clique number}. Similarly, let $\dichi(D)$ denote the \emph{dichromatic number} of a digraph $D$ and let $\omega(D)$ denote the clique number of the underlying undirected graph of $D$. In the second part of this thesis, we consider questions of $\chi$-boundedness and $\dichi$-boundedness. In the undirected setting, the question of $\chi$-boundedness concerns, for a class $\mathcal{C}$ of graphs, for what functions $f$ (if any) is it true that $\chi(G) \le f(\omega(G))$ for all graphs $G \in \mathcal{C}$. In a similar way, the notion of $\dichi$-boundedness refers to, given a class $\mathcal{C}$ of digraphs, for what functions $f$ (if any) is it true that $\dichi(D) \le f(\omega(D))$ for all digraphs $D \in \mathcal{C}$. It was a well-known conjecture, sometimes attributed to Esperet, that for all $k,r \in \mathbb{N}$ there exists $n$ such that in every graph with $G$ with $\chi(G) \ge n$ and $\omega(G) \le k$, there exists an induced subgraph $H$ of $G$ with $\chi(H) \ge r$ and $\omega(H) = 2$. We disprove this conjecture. Then, we examine the class of $k$-chordal digraphs, which are digraphs such that all induced directed cycles have length equal to $k$. We show that for $k \ge 3$, the class of $k$-chordal digraphs is not $\dichi$-bounded, generalizing a result of Aboulker, Bousquet, and de Verclos in [1] for $k=3$. Then we give a hardness result for determining whether a digraph is $k$-chordal, and finally we show a result in the positive direction, namely that the class of digraphs which are $k$-chordal and also do not contain an induced directed path on $k$ vertices is $\dichi$-bounded. We discuss the work of others stemming from and related to our results in both areas, and outline directions for further work.en
dc.language.isoenen
dc.publisherUniversity of Waterlooen
dc.subjectStructural Graph Theoryen
dc.subjectExtremal Graph Theoryen
dc.titleCycles and coloring in graphs and digraphsen
dc.typeMaster Thesisen
dc.pendingfalse
uws-etd.degree.departmentCombinatorics and Optimizationen
uws-etd.degree.disciplineCombinatorics and Optimizationen
uws-etd.degree.grantorUniversity of Waterlooen
uws-etd.degreeMaster of Mathematicsen
uws-etd.embargo.terms0en
uws.contributor.advisorSpirkl, Sophie
uws.contributor.affiliation1Faculty of Mathematicsen
uws.published.cityWaterlooen
uws.published.countryCanadaen
uws.published.provinceOntarioen
uws.typeOfResourceTexten
uws.peerReviewStatusUnrevieweden
uws.scholarLevelGraduateen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record


UWSpace

University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages