Dense arbitrarily vertex decomposable graphs

DOI10.1007/s00373-011-1077-3zbMath1256.05136OpenAlexW2135700202MaRDI QIDQ1928285

Mirko Horňák, Ingo Schiermeyer, Mariusz Woźniak, Antoni Marczyk

Publication date: 3 January 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1077-3

zbMATH Keywords

independence numberperfect matchingtraceable grapharbitrarily vertex decomposable graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items

More aspects of arbitrarily partitionable graphs ⋮ Partitioning powers of traceable or Hamiltonian graphs ⋮ Dense arbitrarily partitionable graphs ⋮ Unnamed Item ⋮ Arbitrary partitionability of product graphs ⋮ On three polynomial kernels of sequences for arbitrarily partitionable graphs ⋮ Partitioning the Cartesian product of a tree and a cycle ⋮ Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs

Cites Work

• On-line arbitrarily vertex decomposable trees
• Arbitrarily vertex decomposable suns with few rays
• On-line arbitrarily vertex decomposable suns
• A lower bound for the circumference of a graph
• Decomposable trees: A polynomial algorithm for tripodes
• A degree bound on decomposable trees
• On arbitrarily vertex decomposable trees
• Note on Hamilton Circuits
• Arbitrarily vertex decomposable caterpillars with four or five leaves
• A homology theory for spanning tress of a graph
• An Ore-type condition for arbitrarily vertex decomposable graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item