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

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

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

• 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?)
• 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
• 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

(11)

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