Subgraphs of graphs. I

DOI10.1016/0012-365X(74)90119-8MaRDI QIDQ1846887zbMATH OpenWikidataFDO

Authors Paul A. Catlin

Publication date 1974

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(74)90119-8

zbMATH Keywords

maximum degree of verticesminimum degree of verticessimple graphssubgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

Let \(G\) and \(H\) be two simple graphs on \(g\) vertices. We give a sufficient condition, based on the minimum degree of the vertices of \(G\) and the maximum degree of the vertices of \(H\), for \(H\) to be a subgraph of \(G\).

Recommendations

• Subgraphs of minimal degree \(k\)
• scientific article; zbMATH DE number 3959468
• scientific article; zbMATH DE number 4065028
• scientific article; zbMATH DE number 4065027
• Graphs with unavoidable subgraphs with large degrees

Cites work

• A Theorem on General Measure Functions
• Transversal theory. An account of some aspects of combinatorial mathematics

Cited in

(39)

• Ore-type conditions implying 2-factors consisting of short cycles
• Two theorems on packings of graphs
• Forbidden graphs for degree and neighbourhood conditions
• On the combinatorial problems which I would most like to see solved
• An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
• On packing bipartite graphs
• Packing of partial designs
• Packing bipartite graphs
• Nonexistence of universal graphs without some trees
• Packing two graphs of even girth 10
• Packing of graphs - a survey
• A near packing of two graphs
• Graphs containing every 2-factor
• Typical and extremal aspects of friends-and-strangers graphs
• Connectivity of friends-and-strangers graphs on random pairs
• On the bipartite graph packing problem
• An Ore-type analogue of the Sauer-Spencer theorem
• Spanning subgraphs with specified valencies. (Reprint)
• Isoperimetric numbers of graphs
• An approximate version of the tree packing conjecture
• A list version of graph packing
• A hypergraph version of a graph packing theorem by Bollobás and Eldridge
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Some results on placing bipartite graphs of maximum degree two
• Betti numbers of subgraphs
• Efficient graph packing via game colouring
• Packing two copies of a sparse graph into a graph with restrained maximum degree
• Embedding graphs in their complements
• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• scientific article; zbMATH DE number 747033 (Why is no real title available?)
• Packing graphs of bounded codegree
• scientific article; zbMATH DE number 6770116 (Why is no real title available?)
• Packing two trees into a graph with restrained maximum degree
• A generalization of the graph packing theorems of Sauer-Spencer and Brandt
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• The Turán number of sparse spanning graphs
• Subgraphs with triangular components
• Graph factors and factorization: 1985--2003: a survey
• On a graph packing conjecture by Bollobás, Eldridge and Catlin

This page was built for publication: Subgraphs of graphs. I

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