论文标题
边缘着色和常规图上的圆形流
Edge colorings and circular flows on regular graphs
论文作者
论文摘要
令$ ϕ_c（g）$为无用的图形$ g $的循环流数。在[常规图的边缘色和圆流流量中，J。Graph Doemhy 79（2015）1-7]，证明，对于每一个$ t \ geq 1 $，$ g $，$ g $都是$（2T+1）$ - 常规图，带有$ ϕ_c（g） \ frac {2} {2T-1} \} $，并且仅当$ g $具有完美匹配的$ m $，以便$ g-m $是双方。这意味着$ g $是1类图形。对于$ t = 1 $，所有大于4的圆流数的图形均为2类图形。我们为所有$ t \ geq 1 $，$ 2 + \ frac {2} {2t-1} = \ inf \ {ϕ_c（g）\ colon g \ text {is a}（2t + 1）\ text { - regular class}这是在常规图的边缘色和圆流数字中猜想的，此外，我们证明$ \ inf \ {ϕ_c（g）\ colon g $是$（2T + 1）$ - 常规类$ 1 $ graph，没有完美匹配，其删除留下了双分式图$ \} = 2 + \ frac {2} {2} {2t-t-1} $。我们进一步反驳了这样一个猜想，即每个$（2T+1）$ - 常规类$ 1 $ Graph最多有$ 2+\ frac {2} {t} $。
Let $ϕ_c(G)$ be the circular flow number of a bridgeless graph $G$. In [Edge-colorings and circular flow numbers of regular graphs, J. Graph Theory 79 (2015) 1-7] it was proved that, for every $t \geq 1$, $G$ is a bridgeless $(2t+1)$-regular graph with $ϕ_c(G) \in \{2+\frac{1}{t}, 2 + \frac{2}{2t-1}\}$ if and only if $G$ has a perfect matching $M$ such that $G-M$ is bipartite. This implies that $G$ is a class 1 graph. For $t=1$, all graphs with circular flow number bigger than 4 are class 2 graphs. We show for all $t \geq 1$, that $2 + \frac{2}{2t-1} = \inf \{ ϕ_c(G)\colon G \text{ is a } (2t+1) \text{-regular class } 2 \text{ graph}\}$. This was conjectured to be true in [Edge-colorings and circular flow numbers of regular graphs, J. Graph Theory 79 (2015) 1-7]. Moreover we prove that $\inf\{ ϕ_c(G)\colon G $ is a $ (2t+1)$-regular class $1$ graph with no perfect matching whose removal leaves a bipartite graph$ \} = 2 + \frac{2}{2t-1}$. We further disprove the conjecture that every $(2t+1)$-regular class $1$ graph has circular flow number at most $2+\frac{2}{t}$.
