A PPA parity theorem about trees in a bipartite graph

DOI10.1016/j.dam.2020.03.064zbMath1479.05298OpenAlexW3017741487WikidataQ113877257 ScholiaQ113877257MaRDI QIDQ2064287

Kathie Cameron, Jack Edmonds

Publication date: 5 January 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.03.064

zbMATH Keywords

Smith's theoremBerman's theoremThomason's theorem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Related Items (1)

Cycles containing all the odd-degree vertices

Cites Work

• Exponentiality of the exchange algorithm for finding another room-partitioning
• Chords in longest cycles
• Parity results on connected f-factors
• Some graphic uses of an even number of odd nodes
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• On the complexity of the parity argument and other inefficient proofs of existence
• Cycles containing all the odd-degree vertices
• Euler Complexes
• Colouring Some Classes of Perfect Graphs Robustly
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE
• Understanding PPA-completeness
• On Hamiltonian Circuits
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

This page was built for publication: A PPA parity theorem about trees in a bipartite graph