A New Characterization of P 6-Free Graphs

DOI10.1007/978-3-540-69733-6_41MaRDI QIDQ3511353zbMATH OpenOpenAlexFDO

Authors Pim Van 't Hof, Daniël Paulusma

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_41

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A new characterization of \(P_{6}\)-free graphs
• A new characterization of P_k-free graphs
• A New Characterization of P_k-free Graphs
• Dominating subgraphs in graphs with some forbidden structures
• Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Note on "The Comparability Graph of a Tree"
• Characterization of \(P_{6}\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Dominating Bipartite Subgraphs in Graphs
• Dominating subgraphs in graphs with some forbidden structures
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1247724 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On a property of the class of n-colorable graphs
• The Comparability Graph of a Tree
• The complexity of coloring graphs without long induced paths

Cited in

(12)

• Dominating subgraphs in graphs with some forbidden structures
• On the chromatic number of (\(P_6\), diamond)-free graphs
• A New Characterization of P_k-free Graphs
• A new characterization of P_k-free graphs
• Choosability of P 5-Free Graphs
• Irredundance perfect andP6-free graphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• On maximum independent sets in \(P_{5}\)-free graphs
• Perfect edge domination in P₆-free graphs and in graphs without efficient edge dominating sets
• Characterization of \(P_{6}\)-free graphs
• A new characterization of \(P_{6}\)-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 Q3511353)