On graphs with limited number of P₄-partners

DOI10.1142/S0129054199000083MaRDI QIDQ5248994zbMATH OpenFDO

Authors F. Roussel, Irena Rusu, Henri Thuillier

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054199000083

zbMATH Keywords

\(P_{4}\)-structuremodular decompositionperfectness

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Efficient algorithms for graphs with few P₄'s
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• On extended P₄-reducible and extended P₄-sparse graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• Clique-width of partner-limited graphs

Cites work

• \(P_{4}\)-laden graphs: A new class of brittle graphs
• A semi-strong perfect graph theorem
• Isomorphism of chordal (6, 3) graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
• On the sibling-structure of perfect graphs
• On the structure of graphs with few P₄s
• Recognizing P₄ -Sparse Graphs in Linear Time
• Some classes of perfectly orderable graphs
• The splittance of a graph
• Transitiv orientierbare Graphen

Cited in

(8)

• Clique-width of partner-limited graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• The packing coloring problem for lobsters and partner limited graphs
• Polynomial instances of the packing coloring problem
• On -sparse graphs and other families
• Efficient algorithms for graphs with few P₄'s
• Partitioning P₄-tidy graphs into a stable set and a forest
• Grundy dominating sequences on X-join product

This page was built for publication: On graphs with limited number of \(P_{4}\)-partners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248994)