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

DOI10.1016/J.DISC.2009.04.022MaRDI QIDQ968408zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• Path factors in subgraphs
• 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
• Path factors and parallel knock-out schemes of almost claw-free graphs
• Isolated toughness and path-factor uniform graphs. II.

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)