Packings by Complete Bipartite Graphs

DOI10.1137/0607024zbMath0597.05050OpenAlexW2028696249MaRDI QIDQ3728943

David G. Kirkpatrick, Pavol Hell

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607024

zbMATH Keywords

complete bipartite graphs\({\mathcal B}\)-factor\({\mathcal B}\)-packing

Mathematics Subject Classification ID

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

Related Items (27)

Looking at the stars ⋮ Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ On matroids induced by packing subgraphs ⋮ Optimal packing of induced stars in a graph ⋮ Quantifying hierarchical conflicts in homology statements ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Unnamed Item ⋮ On the complexity of some edge-partition problems for graphs ⋮ Rounding in symmetric matrices and undirected graphs ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Edge decompositions and rooted packings of graphs ⋮ Packing 3-vertex paths in claw-free graphs and related topics ⋮ Maximum tree-packing in time O(n5/2) ⋮ Packing 2- and 3-stars into cubic graphs ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ How many matchings cover the nodes of a graph? ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ On caterpillar factors in graphs ⋮ On the use of augmenting chains in chain packings ⋮ A parameter linked with \(G\)-factors and the binding number ⋮ On the tree packing problem ⋮ Oriented star packings ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ Generalized partitions of graphs ⋮ Edge decompositions into two kinds of graphs ⋮ Chain packing in graphs ⋮ Packings by cliques and by finite families of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On factors with given components
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Packings by cliques and by finite families of graphs
• F-factors of graphs: A generalized matching problem
• A matching problem with side conditions
• On generalized matching problems
• Packing subgraphs in a graph
• Another look at the degree constrained subgraph problem
• An extension of Tutte's 1-factor theorem
• On the Complexity of General Graph Factor Problems
• TWO THEOREMS IN GRAPH THEORY
• Testing Deadlock-Freedom of Computer Systems
• A Theorem on k-Saturated Graphs
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem
• Maximum matching and a polyhedron with 0,1-vertices
• Subgraphs with prescribed valencies
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Factorization of Linear Graphs
• Reguläre Faktoren von Graphen.
• The Factors of Graphs

This page was built for publication: Packings by Complete Bipartite Graphs