Hyperbolic families and coloring graphs on surfaces-猫眼课题宝

DOI：

10.1090/btran/26

发表时间：

2016-09

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Luke Postle;R. Thomas

设$G$是嵌入到亏格为$g$的固定曲面$\Sigma$中的图，$L=（L（v）：v\in V（G））$是一个列表集合，使得每个列表的大小至少为5，或者每个列表的大小至少为4，并且$G$是无三角形的，或者每个列表的大小至少为3，并且$G$没有长度为4或更小的圈.$G$的$L$-染色是一个映射$\phi$，其定义域为$V（G）$，使得$\phi（v）\in L（v）$对V（G）$中的每一个$v\in，$\phi（v）\ne\phi（u）$对V（G）$中的每一对相邻顶点$u，v\.我们证明了 * 如果$G$中的每个非零同伦圈的长度为$\Omega（\log g）$，则$G$有$L$-染色，* 如果$G$不具有$L$-染色，但每个真子图具有$L$-染色（“$L$-临界图”），则$|V（G）|=O（g）$，* 如果$G$中的每个非零同伦圈的长度为$\Omega（g）$，并且从相应的列表中预着色成对距离为$\Omega（1）$的顶点的集合$X\subseteq V（G）$，则预着色扩展到$G$的$L$-着色，* 如果$G$中的每个非零同伦圈的长度为$\Omega（g）$，并且允许图$G$有交叉，但是每两个交叉都在距离$\Omega（1）$处，则$G$有$L$-染色，并且 * 如果$G$至少有一个$L$-染色，则它至少有$2^{\Omega（|V（G）|）}$ distinct $L$-着色。我们表明，上述断言的后果，一定的等周不等式满足$L$-临界图，我们研究的嵌入式图，满足这些不等式的家庭的结构。由此可见，上述断言适用于其他着色问题，只要相应的临界图满足相同的不等式。

Let $G$ be a graph embedded in a fixed surface $\Sigma$ of genus $g$ and let $L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $G$ is triangle-free, or each list has size at least three and $G$ has no cycle of length four or less. An $L$-coloring of $G$ is a mapping $\phi$ with domain $V(G)$ such that $\phi(v)\in L(v)$ for every $v\in V(G)$ and $\phi(v)\ne\phi(u)$ for every pair of adjacent vertices $u,v\in V(G)$. We prove * if every non-null-homotopic cycle in $G$ has length $\Omega(\log g)$, then $G$ has an $L$-coloring, * if $G$ does not have an $L$-coloring, but every proper subgraph does ("$L$-critical graph"), then $|V(G)|=O(g)$, * if every non-null-homotopic cycle in $G$ has length $\Omega(g)$, and a set $X\subseteq V(G)$ of vertices that are pairwise at distance $\Omega(1)$ is precolored from the corresponding lists, then the precoloring extends to an $L$-coloring of $G$, * if every non-null-homotopic cycle in $G$ has length $\Omega(g)$, and the graph $G$ is allowed to have crossings, but every two crossings are at distance $\Omega(1)$, then $G$ has an $L$-coloring, and * if $G$ has at least one $L$-coloring, then it has at least $2^{\Omega(|V(G)|)}$ distinct $L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.

Hyperbolic families and coloring graphs on surfaces

文献摘要

相似文献