A new characterization of \(P_{6}\)-free graphs

DOI10.1016/j.dam.2008.08.025zbMath1225.05145OpenAlexW2987461903MaRDI 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

zbMATH Keywords

pathscomputational complexitycyclescomplete bipartite graphinduced subgraphsdominating set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

A new characterization of \(P_k\)-free graphs ⋮ The maximum size of an edge 2-neighborhood in \(P_5\)-free graphs ⋮ Laplacian integral graphs with a given degree sequence constraint ⋮ The signature of chordal graphs and cographs ⋮ A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ The price of connectivity for dominating set: upper bounds and complexity ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ On partitioning a graph into two connected subgraphs ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ Prime graphs, matchings and the Castelnuovo-Mumford regularity ⋮ On indicated coloring of some classes of graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Partitioning graphs into connected parts ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

Cites Work

• Characterization of \(P_{6}\)-free graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A simple linear time algorithm for cograph recognition
• Clique-width for 4-vertex forbidden subgraphs
• A Linear Recognition Algorithm for Cographs
• The Comparability Graph of a Tree
• Graph Classes: A Survey
• Dominating Bipartite Subgraphs in Graphs
• A Note on "The Comparability Graph of a Tree"
• LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P₆-FREE GRAPHS
• Dominating cliques in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new characterization of \(P_{6}\)-free graphs