Partitions of graphs into one or two independent sets and cliques
From MaRDI portal
Publication:1917483
DOI10.1016/0012-365X(94)00296-UzbMath0853.68140WikidataQ126550364 ScholiaQ126550364MaRDI QIDQ1917483
Publication date: 12 December 1996
Published in: Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (43)
Groups that have a partition by commuting subsets ⋮ Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ On equistable, split, CIS, and related classes of graphs ⋮ A note on the computational complexity of graph vertex partition ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Counting List Matrix Partitions of Graphs ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ On the complexity of coloring ‐graphs ⋮ On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ \((k,l)\)-colourings and Ferrers diagram representations of cographs ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ Some properties of various graphs associated with finite groups ⋮ The complexity for partitioning graphs by monochromatic trees, cycles and paths ⋮ Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees ⋮ Recognition of split-graphic sequences ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Rainbow graph splitting ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Graph partitions with prescribed patterns ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs ⋮ The complexity of some problems related to GRAPH 3-COLORABILITY ⋮ Partitioning chordal graphs into independent sets and cliques ⋮ Partitioning graphs into complete and empty graphs ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems ⋮ Unnamed Item ⋮ Partitioning cographs into cliques and stable sets ⋮ Characterizing –partitionable Cographs ⋮ Partitions and well-coveredness: the graph sandwich problem ⋮ Packing \(r\)-cliques in weighted chordal graphs ⋮ List matrix partitions of chordal graphs
Cites Work
This page was built for publication: Partitions of graphs into one or two independent sets and cliques
