Induced matchings in cubic graphs

Peter Horák, Qing He, William T. TrotterJournal of Graph Theory 1993 · DOI

Abstract

Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdös and Nešetřil: For each d ≥ 3, the edge set of a graph of maximum degree d can always be partitioned into [5 d 2 /4] subsets each of which induces a matching. © 1993 John Wiley & Sons, Inc.
BibTeX
@article{horak1993induced,
  author = {Peter Horák and Qing He and William T. Trotter},
  title = {{Induced matchings in cubic graphs}},
  journal = {Journal of Graph Theory},
  year = {1993},
  doi = {10.1002/jgt.3190170204},
}

Loading related content...

Figure