论文标题
圆形色的签名图
Circular chromatic number of signed graphs
论文作者
论文摘要
签名的图是一对$（g，σ）$，其中$ g $是图形，$σ：e（g）\ to \ {+， - \} $是一个签名，可以分配给$ g $ a标志的每个边缘。已经研究了签名图的各种概念。在本文中，我们将图形的圆形着色扩展到签名图。 Given a signed graph $(G, σ)$ a circular $r$-coloring of $(G, σ)$ is an assignment $ψ$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $σ(e)=+$, then $ψ(u)$ and $ψ(v)$ have distance at least $1$, and if $σ（e）= - $，然后$ψ（v）$和$ψ（u）$的抗焦点至少$ 1 $。符号图$（g，σ）$的圆形色度$χ_c（g，σ）$是$ r $的最低$ r $（g，σ）$的圆形$ r $ $颜色。对于图$ g $，我们将$ g $的符号圆形色数定义为$ \ max \ {χ_c（g，σ）：σ\ text {是$ g $} \} $的签名。 我们研究签名图的圆形着色的基本特性，并开发用于计算$χ_c（g，σ）$的工具。我们探讨了圆形色度数与符号圆形色的图形数之间的关系，并针对某些图的符号圆形色数呈现边界。特别是，我们确定了$ k $ chromation图形的符号圆形色素的最高图，简单的两部分平面图，$ d $ - 定位图，简单的外平面图和串联式 - 偏见图。我们构造了一个签名的平面简单图，其圆形色度为$ 4+\ frac {2} {3} $。这是基于Kardos和Narboni建造的签名图，作为对Máčajová，Raspaud和škoviera的猜想的反例。
A signed graph is a pair $(G, σ)$, where $G$ is a graph and $σ: E(G) \to \{+, -\}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs. Given a signed graph $(G, σ)$ a circular $r$-coloring of $(G, σ)$ is an assignment $ψ$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $σ(e)=+$, then $ψ(u)$ and $ψ(v)$ have distance at least $1$, and if $σ(e)=-$, then $ψ(v)$ and the antipodal of $ψ(u)$ have distance at least $1$. The circular chromatic number $χ_c(G, σ)$ of a signed graph $(G, σ)$ is the infimum of those $r$ for which $(G, σ)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $\max\{χ_c(G, σ): σ\text{ is a signature of $G$}\}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $χ_c(G, σ)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+\frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of Máčajová, Raspaud, and Škoviera.
