Coloring-flow duality of embedded graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Coloring-flow duality of embedded graphs

Authors:	Matt DeVos Luis Goddyn Bojan Mohar Dirk Vertigan Xuding Zhu

Institution:	Department of Mathematics, Princeton University, Princeton, New Jersey 08544 ; Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6 ; Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia ; Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803-4918 ; Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan

Abstract:	Let be a directed graph embedded in a surface. A map $\phi : E(G) \rightarrow \mathbb{R}$ is a tension if for every circuit $C \subseteq G$ , the sum of $\phi$ on the forward edges of is equal to the sum of $\phi$ on the backward edges of . If this condition is satisfied for every circuit of which is a contractible curve in the surface, then $\phi$ is a local tension. If $1 \le \vert\phi(e)\vert \le \alpha-1$ holds for every $e \in E(G)$ , we say that $\phi$ is a (local) $\alpha$ -tension. We define the circular chromatic number and the local circular chromatic number of by $\chi_{\rm c}(G) =\inf \{\alpha \in \mathbb{R}\mid \mbox{$G$ has an $\alpha$ -tension} \}$ and $\chi_{\rm loc}(G) = \inf \{ \alpha \in \mathbb{R}\mid \mbox{$G$\space has a local $\alpha$ -tension} \}$ , respectively. The invariant $\chi_{\rm c}$ is a refinement of the usual chromatic number, whereas $\chi_{\rm loc}$ is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual . From the definitions we have $\chi_{\rm loc}(G) \le \chi_{\rm c}(G)$ . The main result of this paper is a far-reaching generalization of Tutte's coloring-flow duality in planar graphs. It is proved that for every surface $\mathbb{X}$ and every $\varepsilon > 0$ , there exists an integer so that $\chi_{\rm c}(G) \le \chi_{\rm loc}(G)+\varepsilon$ holds for every graph embedded in $\mathbb{X}$ with edge-width at least , where the edge-width is the length of a shortest noncontractible circuit in . In 1996, Youngs discovered that every quadrangulation of the projective plane has chromatic number 2 or 4, but never 3. As an application of the main result we show that such `bimodal' behavior can be observed in $\chi_{\rm loc}$ , and thus in $\chi_{\rm c}$ for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if is embedded in some surface with large edge-width and all its faces have even length $\le 2r$ , then $\chi_{\rm c}(G)\in 2,2+\varepsilon] \cup \frac{2r}{r-1},4]$ . Similarly, if is a triangulation with large edge-width, then $\chi_{\rm c}(G)\in 3,3+\varepsilon] \cup 4,5]$ . It is also shown that there exist Eulerian triangulations of arbitrarily large edge-width on nonorientable surfaces whose circular chromatic number is equal to 5.

Keywords:	Graph theory coloring flow tension local tension circular chromatic number surface edge-width triangulation quadrangulation locally bipartite

	点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息
	点击此处可从《Transactions of the American Mathematical Society》下载免费的PDF全文

设为首页 | 免责声明 | 关于勤云 | 加入收藏