Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2412.11774 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912674436087808 |
|---|---|
| author | Cambie, Stijn Dross, François Knauer, Kolja La, Hoang Valicov, Petru |
| author_facet | Cambie, Stijn Dross, François Knauer, Kolja La, Hoang Valicov, Petru |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11774 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitions of planar (oriented) graphs into a connected acyclic and an independent set Cambie, Stijn Dross, François Knauer, Kolja La, Hoang Valicov, Petru Combinatorics Discrete Mathematics O5Cxx 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. |
| title | Partitions of planar (oriented) graphs into a connected acyclic and an independent set |
| topic | Combinatorics Discrete Mathematics O5Cxx |
| url | https://arxiv.org/abs/2412.11774 |