A new characterization of \(P_{6}\)-free graphs
From MaRDI portal
Publication:972332
DOI10.1016/j.dam.2008.08.025zbMath1225.05145MaRDI QIDQ972332
Daniël Paulusma, Pim van 't Hof
Publication date: 25 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.025
paths; computational complexity; cycles; complete bipartite graph; induced subgraphs; dominating set
05C35: Extremal problems in graph theory
05C38: Paths and cycles
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)