CEU Electronic Theses and Dissertations, 2020
| Author | Colucci Cavalcante de Souza, Lucas |
|---|---|
| Title | Coloring Results in Some Extremal Problems |
| Summary | This thesis deals with three types of problems in Graph Theory related, in different forms, to colorings of graphs. In the first chapter, we study the well-known edge-disjoint paths problem in a setting introduced by Csaba, Faudree, Gyárfás, Lehel, and Schelp and give new bounds on the maximum degree of a multigraph $D$ that guarantees that it is realizable in a complete bipartite base graph $K_{n,n}$ on the same vertex set, both assuming that $D$ is bipartite with respect to the bipartition classes of $K_{n,n}$ and without this assumption. We also give sharp results on the number of edges that $D$ may have to guarantee that $K_{n,n}$ is terminal-pairable with respect to $D$. This generalizes the work of Gy\H{o}ri, Mezei and Mészáros on complete base graphs. In our proofs, edge colorings of multigraphs are used and we apply the celebrated result of Kahn on the list chromatic index of multigraphs along with other more classical result on edge colorings. In the second chapter, the well-studied problem of $L(2,1)$-labelings of graphs, a vertex color where the colors satisfy some distance restrictions, is studied. We focus on oriented graphs, and prove an analogous result of Griggs and Yeh in this setting about bounds on the $L(2,1)$ number in terms of the maximum degree of the graph and related parameters. We introduce alternative versions of the $L(2,1)$-labeling problem and prove similar results for these new problems raised. Finally, we improve some results of Jiang, Shao and Vesel on the $L(2,1)$ number of product of oriented cycles. In the third chapter, we consider the problem of Erd\H{o}s and Rothschild of determining the maximum number of edge colorings without a monochromatic copy of a fixed subgraph that a graph on $n$ vertices may admit. More especifically, we improve the results of Hoppen, Kohayakawa and Lefmann when the monochromatic forbidden subgraph is a star. |
| Supervisor | Gyori Ervin |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2020/colucci_lucas.pdf |
Visit the CEU Library.
© 2007-2021, Central European University