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

zbMATH Keywords

computational complexitypathsdominating setcyclesinduced subgraphscomplete bipartite graph

Mathematics Subject Classification ID

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Linear Recognition Algorithm for Cographs
• A Note on "The Comparability Graph of a Tree"
• A simple linear time algorithm for cograph recognition
• Characterization of \(P_{6}\)-free graphs
• Clique-width for 4-vertex forbidden subgraphs
• Dominating Bipartite Subgraphs in Graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating cliques in graphs
• Dominating subgraphs in graphs with some forbidden structures
• Graph Classes: A Survey
• LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P₆-FREE GRAPHS
• The Comparability Graph of a Tree
• The complexity of coloring graphs without long induced paths

Cited In (25)

• 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
• 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
• Laplacian integral graphs with a given degree sequence constraint
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• 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)