On partitioning the edges of an infinite digraph into directed cycles

DOI10.19086/AIC.18702MaRDI QIDQ5162866zbMATH OpenOpenAlexFDO

Authors Attila Joó

Publication date 5 November 2021

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1704.08830

zbMATH Keywords

directed cycleedge-partitioninfinite digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Nash-Williams proved that for an undirected graph $G$ the set $E(G)$ can be partitioned into cycles if and only if every cut has either even or infinite number of edges. Later C. Thomassen gave a simpler proof for this and conjectured the following directed analogue of the theorem: the edge set of a digraph can be partitioned into directed cycles if and only if for each subset of the vertices the cardinality of the ingoing and the outgoing edges are equal. The aim of the paper is to prove this conjecture.

Recommendations

• Nash-Williams' cycle-decomposition theorem
• Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles
• Partitions of digraphs into paths or circuits
• scientific article; zbMATH DE number 4091535
• The directed path partition conjecture

Cites work

• Decomposition of Graphs Into Closed and Endless Chains
• Elementary submodels in infinite combinatorics
• Nash-Williams' cycle-decomposition theorem

Cited in

(5)

• Nash-Williams' cycle-decomposition theorem
• Reducing the dichromatic number via cycle reversions in infinite digraphs
• The Lovász-Cherkassky theorem in countable graphs
• On the infinite Lucchesi–Younger conjecture I
• Circuit-partition of infinite matroids

This page was built for publication: On partitioning the edges of an infinite digraph into directed cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162866)