Partitions of Planar (Oriented) Graphs into a Connected Acyclic and an Independent Set

Read full text
Authors: Stijn Cambie, François Dross, Kolja B. Knauer, Hoang La, Petru Valicov
Cited by: 0
References: 2

Abstract

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.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Limits and Structures in Graph Theory

Publication details

Journal / source
The Electronic Journal of Combinatorics
Volume
33
Issue
1
Pages
27–34
Publication date
13 February 2026
Language
EN