A proof of Cunningham's conjecture on restricted subgraphs and jump systems
From MaRDI portal
Publication:444382
DOI10.1016/j.jctb.2012.03.003zbMath1244.05181OpenAlexW1983199941MaRDI QIDQ444382
Kenjiro Takazawa, Yusuke Kobayashi, Jácint Szabó
Publication date: 14 August 2012
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2012.03.003
degree sequencejump systemsquare-free 2-matching\(K_{t,t}\)-free \(t\)-matching\(M\)-convex function
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (10)
Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ Triangle-free 2-matchings and M-concave functions on jump systems ⋮ A note on M-convex functions on jump systems ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ A survey of fundamental operations on discrete convex functions of various kinds ⋮ On basic operations related to network induction of discrete convex functions ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
Cites Work
- Unnamed Item
- Unnamed Item
- An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
- A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
- An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs
- Convexity and Steinitz's exchange property
- Combinatorial algorithms for matchings, even factors and square-free 2-factors
- Valuated matroids: A new look at the greedy algorithm
- \(\Delta\)-matroid and jump system
- Induction of M-convex functions by linking systems
- Some combinatorial properties of discriminants in metric vector spaces
- Pseudomatroids
- A matching problem with side conditions
- A greedy-algorithm characterization of valuated \(\Delta\)-matroids
- Valuated matroids
- \(\Delta\)-matroids with the strong exchange conditions
- The membership problem in jump systems
- Restricted \(t\)-matchings in bipartite graphs
- Pfaffian forms and \(\Delta\)-matroids
- Matching, matroids, and extensions
- Polyhedron of triangle-free simple 2-matchings in subcubic graphs
- Finding maximum square-free 2-matchings in bipartite graphs
- Even factors, jump systems, and discrete convexity
- Submodular functions and optimization.
- Maximum Cardinality Simple 2-matchings in Subcubic Graphs
- A Weighted kt, t-Free t-Factor Algorithm for Bipartite Graphs
- On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
- Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
- Restricted b-Matchings in Degree-Bounded Graphs
- Greedy algorithm and symmetric matroids
- Discrete Convex Analysis
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Operations on M‐Convex Functions on Jump Systems
- M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
- Integer Programming and Combinatorial Optimization
This page was built for publication: A proof of Cunningham's conjecture on restricted subgraphs and jump systems
