Path factors and parallel knock-out schemes of almost claw-free graphs

DOI10.1016/J.DISC.2009.04.022zbMATH Open1219.05140OpenAlexW2030294818MaRDI QIDQ968408FDOQ968408

Authors: Matthew Johnson, Daniël Paulusma, Chantal Wood 

Publication date: 5 May 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/7415/1/7415.pdf

Recommendations

• Path factors and parallel knock-out schemes of almost claw-free graphs
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
• Upper bounds and algorithms for parallel knock-out numbers
• Eliminating graphs by means of parallel knock-out schemes
• Mathematical Foundations of Computer Science 2004

zbMATH Keywords

perfect matchingfactor(almost) claw-free graphsparallel knock-out schemes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• On the Complexity of General Graph Factor Problems
• Claw-free graphs---a survey
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Title not available (Why is that?)
• Clique partitions, graph compression and speeding-up algorithms
• On partitioning the edges of graphs into connected subgraphs
• Graph factors and factorization: 1985--2003: a survey
• Title not available (Why is that?)
• 1-Factors and Antifactor Sets
• Almost claw‐free graphs
• Toughness and hamiltonicity in almost claw-free graphs
• Hamiltonian cycles in almost claw-free graphs
• Path factors in claw-free graphs
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Packing paths of length at least two
• Parallel Knockouts in the Complete Graph
• Eliminating graphs by means of parallel knock-out schemes
• Path factors of bipartite graphs
• Path-factors in the square of a tree
• Upper bounds and algorithms for parallel knock-out numbers
• Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
• The computational complexity of the parallel knock-out problem
• Neighborhood intersections and Hamiltonicity in almost claw-free graphs

Cited In (6)

• Some existence theorems on path factors with given properties in graphs
• Component factors and binding number conditions in graphs
• Knocking out \(P_k\)-free graphs
• TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS
• Isolated toughness and path-factor uniform graphs. II.
• Path factors in subgraphs

This page was built for publication: Path factors and parallel knock-out schemes of almost claw-free graphs

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