List monopolar partitions of claw-free graphs

DOI10.1016/J.DISC.2011.08.022MaRDI QIDQ442362zbMATH OpenOpenAlexFDO

Authors Ross Churchley, Jing Huang

Publication date 10 August 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.08.022

zbMATH Keywords

listalgorithmcomplexitymonopolar graphmonopolar partition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Solving partition problems with colour-bipartitions
• The list partition problem for graphs
• On the Polarity and Monopolarity of Graphs
• The Complexity of the List Partition Problem for Graphs
• Monopolar graphs: complexity of computing classical graph parameters

Cites work

• A forbidden subgraph characterization of line-polar bipartite graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Characterizations of derived graphs
• Line-Polar Graphs: Characterization and Recognition
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• Polar permutation graphs
• Polarity of chordal graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(6)

• Partitioning a graph into disjoint cliques and a triangle-free graph
• On the Polarity and Monopolarity of Graphs
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Monopolar graphs: complexity of computing classical graph parameters

This page was built for publication: List monopolar partitions of claw-free graphs

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