Regular subgraphs of almost regular graphs

DOI10.1016/0095-8956(84)90047-9zbMath0527.05059MaRDI QIDQ595688

Gil Kalai, Noga Alon, Shmuel Friedland

Publication date: 1984

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(84)90047-9

zbMATH Keywords

average degree; regular subgraph; Berge-Sauer conjecture; maximal degree

Mathematics Subject Classification ID

05C99: Graph theory

Related Items

Every 4-regular graph plus an edge contains a 3-regular subgraph, Zero-sum problems in finite Abelian groups: a survey, Graph factors and factorization: 1985--2003: a survey, Regular subgraphs of dense graphs, Set systems with no union of cardinality 0 modulo \(m\), Additive bases of vector spaces over prime fields, On Davenport's constant, Colorings and orientations of graphs, On the complexity of the parity argument and other inefficient proofs of existence, Blow-up lemma, On graph decompositions modulo \(k\), Zero-sum problems and coverings by proper cosets, On zero-sum subsequences of restricted size. II., Problems and results in extremal combinatorics. I., On 2-coloring certain \(k\)-uniform hypergraphs, Zero-sum problems -- a survey, Two zero-sum problems and multiple properties, Davenport constant for semigroups., Weight choosability of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• [a,b-factors of graphs]
• Every 4-regular graph plus an edge contains a 3-regular subgraph
• Diophantine problems in variables restricted to the values 0 and 1
• A combinatorial problem on finite Abelian groups. II
• A combinatorial problem on finite Abelian groups. I
• Representations by \(k\)-th powers in \(GF(q)\)
• A remark on the factor theorems of lovász and tutte
• The Subgraph Problem
• Three‐regular subgraphs of four‐regular graphs