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

DOI10.1016/j.disc.2009.04.022zbMath1219.05140OpenAlexW2030294818MaRDI QIDQ968408

Daniël Paulusma, Matthew Johnson, 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

factorperfect matching(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)

Related Items (6)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eliminating graphs by means of parallel knock-out schemes
• Graph factors and factorization: 1985--2003: a survey
• 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
• Claw-free graphs---a survey
• 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
• Clique partitions, graph compression and speeding-up algorithms
• The computational complexity of the parallel knock-out problem
• On the Complexity of General Graph Factor Problems
• On partitioning the edges of graphs into connected subgraphs
• 1-Factors and Antifactor Sets
• Parallel Knockouts in the Complete Graph
• Path factors of bipartite graphs
• Almost claw‐free graphs
• Toughness and hamiltonicity in almost claw-free graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Hamiltonian cycles in almost claw-free graphs
• Neighborhood intersections and Hamiltonicity in almost claw-free graphs
• Path factors in claw-free graphs

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