Packings of graphs and applications to computational complexity
From MaRDI portal
Publication:1250227
DOI10.1016/0095-8956(78)90030-8zbMath0387.05020OpenAlexW2015832457MaRDI QIDQ1250227
Stephen E. Eldridge, Béla Bollobás
Publication date: 1978
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(78)90030-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99) Combinatorial aspects of packing and covering (05B40)
Related Items
An approximate version of the tree packing conjecture, A list version of graph packing, Two theorems on packings of graphs, Extremal Theorems for Degree Sequence Packing and the Two-Color Discrete Tomography Problem, On a packing problem of Alon and Yuster, Packing trees in complete graphs, Embedding digraphs of small size, An Ore-type analogue of the Sauer-Spencer theorem, A note on packing of uniform hypergraphs, Packing of two digraphs into a transitive tournament, The threshold bias of the clique-factor game, Fixed-point-free embeddings of digraphs with small size, Labeled embedding of \((n, n-2)\)-graphs in their complements, Graphs containing every 2-factor, The Erdős-Sós conjecture for spiders of large size, k-Planar Placement and Packing of Δ-Regular Caterpillars, Packing two graphs of even girth 10, Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree, A note on \(k\)-placeable graphs, Placing two edge-disjoint copies of a tree into a bipartite graph, Proof of a Packing Conjecture of Bollobás, Using Brouwer’s Fixed Point Theorem, On Degree Sequences Forcing The Square of a Hamilton Cycle, Degree conditions for the existence of vertex-disjoint cycles and paths: a survey, Near packings of graphs, Packing a number of copies of a \(( p , q )\)-graph, Symmetric edge-decompositions of hypercubes, Some results on the complexity of families of sets, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Efficient Graph Packing via Game Colouring, Packing \(d\)-degenerate graphs, Near packings of two graphs, On packing bipartite graphs, Packing of graphs with small product of sizes, Sparse graphs of girth at least five are packable, On the elusiveness of Hamiltonian property, Embedding graphs in their complements, On embedding graphs with bounded sum of size and maximum degree, On a graph packing conjecture by Bollobás, Eldridge and Catlin, On the Bollobás–Eldridge Conjecture for Bipartite Graphs, Embedding (p,p - 1) graphs in their complements, Almost regular edge colorings and regular decompositions of complete graphs, On the relation of separability, bandwidth and embedding, Labeled 2-packings of trees, Packing Graphs of Bounded Codegree, The Turán number of sparse spanning graphs, Packing of graphs - a survey, Packing two copies of a sparse graph into a graph with restrained maximum degree, A discrepancy version of the Hajnal–Szemerédi theorem, Ore-type conditions implying 2-factors consisting of short cycles, A note on packing two copies of a tree into a graph with small maximum degree, Embedding Graphs Having Ore-Degree at Most Five, Packing graphs in their complements, A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge, A near packing of two graphs, Packing two graphs of order n having total size at most 2n-2, Packing of partial designs, Labeled packing of cycles and circuits
Cites Work
