论文标题
在$ 3 $ - 流向关键图
On $3$-flow-critical graphs
论文作者
论文摘要
如果它不承认无零$ 3 $ -Flow，则无用的图形$ g $称为$ 3 $ - 流向 - 限制性，但$ g/e $对于E（g）$中的任何$ e \ abes。 Tutte的$ 3 $流量猜想可以等效地说明，每个$ 3 $流量的图表都包含一个三分之二的顶点。在本文中，我们研究了$ 3 $ - 流向关键图的结构和极端边缘密度。我们将结构属性应用于$ 3 $流量的图表的密度下限和上限，也就是说，对于$ N $ Vertices上的任何$ 3 $流量的图形$ G $，$ \ frac {8n-n-2} {5} {5} {5} {5} \ le | e（g）我们推测，$ n \ ge 7 $顶点上的每3美元至关重要的图形最多都有$ 3n-8 $的边缘，如果是的话，这将很紧。对于平面图，$ N $ Vertices上$ 3 $ - 流向的最佳密度上限是$ \ frac {5n-8} {2} $，从Kostochka和Yancey（JCTB 2014）闻名（JCTB 2014）在Vertex着色$ 4 $ -Criginal tagrallity tay duality by duality the duality the duality $ 4 $。
A bridgeless graph $G$ is called $3$-flow-critical if it does not admit a nowhere-zero $3$-flow, but $G/e$ has for any $e\in E(G)$. Tutte's $3$-flow conjecture can be equivalently stated as that every $3$-flow-critical graph contains a vertex of degree three. In this paper, we study the structure and extreme edge density of $3$-flow-critical graphs. We apply structure properties to obtain lower and upper bounds on the density of $3$-flow-critical graphs, that is, for any $3$-flow-critical graph $G$ on $n$ vertices, $$\frac{8n-2}{5}\le |E(G)|\le 4n-10,$$ where each equality holds if and only if $G$ is $K_4$. We conjecture that every $3$-flow-critical graph on $n\ge 7$ vertices has at most $3n-8$ edges, which would be tight if true. For planar graphs, the best possible density upper bound of $3$-flow-critical graphs on $n$ vertices is $\frac{5n-8}{2}$, known from a result of Kostochka and Yancey (JCTB 2014) on vertex coloring $4$-critical graphs by duality.
