On the Polarity and Monopolarity of Graphs

DOI10.1002/jgt.21755zbMath1294.05126MaRDI QIDQ5418774

Jing Huang, Ross Churchley

Publication date: 28 May 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21755

zbMATH Keywords

characterization; polynomial time algorithm; NP-completeness; polar graph; claw-free graph; triangle-free graph; monopolar graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, Partitioning a graph into complementary subgraphs, List monopolar partitions of claw-free graphs, Solving partition problems with colour-bipartitions, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Minimal obstructions to \(( \infty , k )\)-polarity in cographs, Minimal obstructions to \(( s , 1 )\)-polarity in cographs, Partitioning a graph into disjoint cliques and a triangle-free graph, Complexity and algorithms for recognizing polar and monopolar graphs, Monopolar graphs: complexity of computing classical graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• List monopolar partitions of claw-free graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Solving partition problems with colour-bipartitions
• 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 cographs