On the Polarity and Monopolarity of Graphs
From MaRDI portal
Publication:5418774
DOI10.1002/jgt.21755zbMath1294.05126OpenAlexW2127629780MaRDI QIDQ5418774
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
characterizationpolynomial time algorithmNP-completenesspolar graphclaw-free graphtriangle-free graphmonopolar graph
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
Monopolar graphs: complexity of computing classical graph parameters ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Minimal obstructions to \(( s , 1 )\)-polarity in cographs ⋮ Unnamed Item ⋮ List monopolar partitions of claw-free graphs ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ Partitioning a graph into complementary subgraphs ⋮ Minimal obstructions to \(( \infty , k )\)-polarity in cographs ⋮ Solving partition problems with colour-bipartitions ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph
Cites Work
- 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
- Unnamed Item
- Unnamed Item
This page was built for publication: On the Polarity and Monopolarity of Graphs
