A New Characterization of P 6-Free Graphs

DOI10.1007/978-3-540-69733-6_41zbMath1148.05316OpenAlexW1708800690MaRDI QIDQ3511353

Daniël Paulusma, Pim van 't Hof

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

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

Related Items (3)

A new characterization of \(P_k\)-free graphs ⋮ Choosability of P 5-Free Graphs ⋮ On maximum independent sets in \(P_{5}\)-free graphs

Cites Work

• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Characterization of \(P_{6}\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On a property of the class of n-colorable graphs
• The Comparability Graph of a Tree
• Graph Classes: A Survey
• Dominating Bipartite Subgraphs in Graphs
• A Note on "The Comparability Graph of a Tree"
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A New Characterization of P 6-Free Graphs