A pair of forbidden subgraphs and perfect matchings.

DOI10.1016/j.jctb.2005.08.002zbMath1090.05057OpenAlexW1988932361MaRDI QIDQ2490834

Michael D. Plummer, Katsuhiro Ota, Ken-ichi Kawarabayashi, Shinya Fujita, Akira Saito, Cláudio Leonardo Lucchesi

Publication date: 18 May 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.08.002

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

A Pair of Forbidden Subgraphs and 2-Factors, Characterizing forbidden pairs for relative length of longest paths and cycles, Strongly spanning trailable graphs with small circumference and Hamilton-connected claw-free graphs, Forbidden set of induced subgraphs for 2-connected supereulerian graphs, Forbidden subgraphs on Hamiltonian index, Forbidden subgraphs generating a finite set, Forbidden induced subgraphs for near perfect matchings, Forbidden subgraphs and the existence of a spanning tree without small degree stems, Forbidden subgraphs and the existence of a 2-walk, Forbidden pairs of disconnected graphs for supereulerianity of connected graphs, Forbidden induced subgraphs for star-free graphs, A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity, Forbidden induced subgraphs for perfect matchings, Pairs of forbidden induced subgraphs for homogeneously traceable graphs, Forbidden Subgraphs Generating Almost the Same Sets, Spectral conditions for graphs to be β-deficient involving minimum degree, Forbidden pairs for equality of connectivity and edge-connectivity of graphs, Forbidden triples for perfect matchings, Forbidden Induced Subgraphs for Toughness, Forbidden subgraphs and the existence of a 2-factor, Forbidden pairs and the existence of a dominating cycle, Perfect Matchings Avoiding Several Independent Edges in a Star-Free Graph, Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3, Forbidden pairs for \(k\)-connected Hamiltonian graphs, Ramsey-type results for path covers and path partitions, A characterization of \(P_5\)-free graphs with a homeomorphically irreducible spanning tree, Minimal forbidden sets for degree sequence characterizations

Cites Work

• Matching theory
• Characterizing forbidden pairs for hamiltonian properties
• On partitioning the edges of graphs into connected subgraphs
• 1-Factors and Antifactor Sets
• Forbidden subgraphs and bounds on the size of a maximum matching
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item