Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 5 of 5 for “"chi-boundedness"”.
-
On coloring digraphs with forbidden induced subgraphs
… number of a digraph $D$, denoted by $\dichi(D)$, is designed to be the directed analog of the chromatic number of a graph $G$, denoted by $\chi(G)$. The field of $\chi$-boundedness studies the induced subgraphs that need to be present in a graph with high chromatic number. In this thesis, …
-
Local properties of graphs with large chromatic number
… \log \omega)$. Lastly, extending the $\chi$-boundedness of circle graphs, we prove a conjecture of Geelen that every proper vertex-minor-closed class of graphs is $\chi$-bounded.
-
Cycles and coloring in graphs and digraphs
… $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 …
-
Preserving and Generalizing χ-boundedness
The notion of χ-boundedness, introduced by Gyárfás in the mid-1980s, captures when, for every induced subgraph of a graph, large chromatic number can occur only due to the presence of a sufficiently large complete subgraph. The study of χ-boundedness is a central topic in graph theory. …
-
Two graph classes with bounded chromatic number
A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic …