A question at the intersection of Barnette's Hamiltonicity and Neumann-Lara's dicoloring conjecture is: Can every Eulerian oriented planar graph be vertex-partitioned into two acyclic sets? A CAI-partition of an undirected/oriented graph is a partition into a tree/connected acyclic subgraph and an independent set. Consider any plane Eulerian oriented triangulation together with its unique tripartition, i.e. partition into three independent sets. If two of these three sets induce a subgraph G that has a CAI-partition, then the above question has a positive answer. We show that if G is subcubic, then it has a CAI-partition, i.e. oriented planar bipartite subcubic 2-vertex-connected graphs admit CAI-partitions. We also show that series-parallel 2-vertex-connected graphs admit CAI-partitions. Finally, we present a Eulerian oriented triangulation such that no two sets of its tripartition induce a graph with a CAI-partition. This generalizes a result of Alt, Payne, Schmidt, and Wood to the oriented setting.
翻译:巴尼特哈密顿性与诺伊曼-拉拉有向着色猜想交叉的一个问题是:每个欧拉有向平面图是否都能被顶点划分为两个无环集?无向/有向图的CAI划分是指将其划分为一棵树/连通无圈子图与一个独立集。考虑任意平面欧拉有向三角剖分及其唯一的三划分(即划分为三个独立集)。若这三个集合中的两个诱导出一个子图G,且G具有CAI划分,则上述问题有肯定答案。我们证明:若G是次三次的,则它具有CAI划分,即有向平面二分次三次2-连通图允许CAI划分。我们还证明:串并联2-连通图允许CAI划分。最后,我们给出一个欧拉有向三角剖分,使得其三划分中任意两个集合诱导的子图均不具有CAI划分。这将阿尔特、佩恩、施密特和伍德的结果推广到了有向图情形。