Coloring and covering problems on graphs

Graph coloring;Graph covering

Loeb, Sarah Jane

关键词: Graph coloring;    Graph covering;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/98358/LOEB-DISSERTATION-2017.pdf?sequence=1&isAllowed=y

美国|英语

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

【 摘 要 】

The \emph{separation dimension} of a graph $G$, written $\pi(G)$, is the minimum number of linear orderings of $V(G)$ such that every two nonincident edges are ``separated'' in some ordering, meaning that both endpoints of one edge appear before both endpoints of the other.We introduce the \emph{fractional separation dimension} $\pi_f(G)$, which is the minimum of $a/b$ such that some $a$ linear orderings (repetition allowed) separate every two nonincident edges at least $b$ times.In contrast to separation dimension, we show fractional separation dimension isbounded: always $\pi_f(G)\le 3$, with equality if and only if $G$ contains $K_4$.There is no stronger bound even for bipartite graphs, since $\pi_f(K_{m,m})=\pi_f(K_{m+1,m})=\frac{3m}{m+1}$.We also compute $\pi_f(G)$ for cycles and some complete tripartite graphs. We show that $\pi_f(G)