A new characterization of P₆-free graphs
DOI10.1016/J.DAM.2008.08.025zbMATH Open1225.05145OpenAlexW2987461903MaRDI QIDQ972332FDOQ972332
Authors: 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
Recommendations
- A New Characterization of P 6-Free Graphs
- Characterization of \(P_{6}\)-free graphs
- A new characterization of \(P_k\)-free graphs
- A New Characterization of $$P_k$$-free Graphs
- Total dominations in \(P_6\)-free graphs
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Irredundance perfect andP6-free graphs
- scientific article; zbMATH DE number 5279372
- 4-colorability of \(P_6\)-free graphs
- Four-coloring \(P_6\)-free graphs
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Title not available (Why is that?)
- The Comparability Graph of a Tree
- Dominating cliques in \(P_ 5\)-free graphs
- The complexity of coloring graphs without long induced paths
- Dominating subgraphs in graphs with some forbidden structures
- A Linear Recognition Algorithm for Cographs
- Title not available (Why is that?)
- Characterization of \(P_{6}\)-free graphs
- A simple linear time algorithm for cograph recognition
- Clique-width for 4-vertex forbidden subgraphs
- A Note on "The Comparability Graph of a Tree"
- Dominating cliques in graphs
- Title not available (Why is that?)
- Dominating Bipartite Subgraphs in Graphs
- LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS
Cited In (26)
- A New Characterization of P 6-Free Graphs
- Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
- Irredundance perfect andP6-free graphs
- 4-coloring \((P_6, \text{bull})\)-free graphs
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Title not available (Why is that?)
- A new characterization of \(P_k\)-free graphs
- The price of connectivity for dominating set: upper bounds and complexity
- The maximum size of an edge 2-neighborhood in \(P_5\)-free graphs
- The signature of chordal graphs and cographs
- Characterization of \(P_{6}\)-free graphs
- Partitioning graphs into connected parts
- Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
- Partitioning Graphs into Connected Parts
- On indicated coloring of some classes of graphs
- New Polynomial Case for Efficient Domination in P 6-free Graphs
- On partitioning a graph into two connected subgraphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
- Laplacian integral graphs with a given degree sequence constraint
- A New Characterization of $$P_k$$-free Graphs
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- Prime graphs, matchings and the Castelnuovo-Mumford regularity
- Finding matching cuts in \(H\)-free graphs
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
This page was built for publication: A new characterization of \(P_{6}\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972332)
