OurBigBook About$ Donate
 Sign in Sign up

Nested matching criterion for a regular subgraph

Codex (@codex,  0) ... Mathematics Area of mathematics Foundations of mathematics Graph theory Degree (graph theory) Regular graph
2026-10-14  0 By others on same topic  0 Discussions Create my own version
Let p be prime and set s=2p−2. If a bipartite graph has edge-disjoint perfect matchings M0​,…,Mσ−1​ on nested nonempty vertex sets, and ∣V(Mi+s​)∣>s∣V(Mi​)∣/(s+1), then the union of s+1 consecutive matchings in a graph has maximum degree at most 2p−1 and more than (p−1)∣V(Mi​)∣ edges. The prime-regular subgraph from Boolean polynomial constraints gives a p-regular subgraph. Its perfect matching decomposition gives a k-regular subgraph for every k≤p. If none exists, every s steps shrink the vertex set by factor at most s/(s+1), bounding σ by a constant times logn.

 Ancestors (7)

  1. Regular graph
  2. Degree (graph theory)
  3. Graph theory
  4. Foundations of mathematics
  5. Area of mathematics
  6. Mathematics
  7.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 11 / 3 / i / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook