List monopolar partitions of claw-free graphs

DOI10.1016/j.disc.2011.08.022zbMath1246.05127OpenAlexW2064696340MaRDI QIDQ442362

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

listcomplexityalgorithmmonopolar graphmonopolar partition

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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