List Partitions

DOI10.1137/S0895480100384055zbMath1029.05143OpenAlexW2911854207WikidataQ105742794 ScholiaQ105742794MaRDI QIDQ4443101

Sulamita Klein, Tomás Feder, Rajeev Motwani, Pavol Hell

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480100384055

zbMATH Keywords

NP-completeness perfect graphs split graphs dichotomy constraint satisfaction problems polynomial time algorithms $H$-colorings graph partitions list homomorphisms 2-joins quasi-polynomial algorithms clique cutsets communication bound skew cutsets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items (84)

One-three join: a graph operation and its consequences ⋮ On the density of trigraph homomorphisms ⋮ Unnamed Item ⋮ Counting $4 \times 4$ matrix partitions of graphs ⋮ Matrix partitions of split graphs ⋮ Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ On the probe problem for $(r, \ell)$-well-coveredness: algorithms and complexity ⋮ Parameterized complexity dichotomy for $(r, \ell)$-\textsc{Vertex Deletion} ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Obstructions to partitions of chordal graphs ⋮ Counting List Matrix Partitions of Graphs ⋮ Subgraph complementation ⋮ Minimal obstructions to 2-polar cographs ⋮ Minimal obstructions to $( s , 1 )$-polarity in cographs ⋮ Disconnected cuts in claw-free graphs ⋮ The $(k, \ell)$ partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Clique versus independent set ⋮ 2K2 vertex-set partition into nonempty parts ⋮ On the complexity of coloring ‐graphs ⋮ Adapted game colouring of graphs ⋮ On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs ⋮ On the adaptable chromatic number of graphs ⋮ List homomorphism: beyond the known boundaries ⋮ 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 ⋮ Extended skew partition problem ⋮ Matrix partitions of perfect graphs ⋮ Unnamed Item ⋮ On the probe problem for $(r,\ell )$-well-coveredness ⋮ The adaptable choosability number grows with the choosability number ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Colouring, constraint satisfaction, and complexity ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ Computing $H$-joins with application to 2-modular decomposition ⋮ Solving problems on generalized convex graphs via mim-width ⋮ List matrix partitions of graphs representing geometric configurations ⋮ The monotonicity property of $M$-partition problems ⋮ Polar cographs ⋮ Polar cographs ⋮ An asymptotically tight bound on the adaptable chromatic number ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ On realizations of point determining graphs, and obstructions to full homomorphisms ⋮ The external constraint 4 nonempty part sandwich problem ⋮ Recognition of split-graphic sequences ⋮ Stable-$\Pi$ partitions of graphs ⋮ $2K_2$-partition of some classes of graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ $2K_{2}$ vertex-set partition into nonempty parts ⋮ A forbidden subgraph characterization of line-polar bipartite graphs ⋮ The computational complexity of disconnected cut and $2 K_2$-partition ⋮ Dense and sparse graph partition ⋮ FindingH-partitions efficiently ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ A note on the recognition of bisplit graphs ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ On the (parameterized) complexity of recognizing well-covered ($r$,$\ell$)-graph ⋮ Minimal obstructions to $( \infty , k )$-polarity in cographs ⋮ Graph partitions with prescribed patterns ⋮ The complexity of list edge-partitions for simple graphs ⋮ Join colourings of chordal graphs ⋮ An upper bound on adaptable choosability of graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Split digraphs ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ Adaptable chromatic number of graph products ⋮ Partitioning graphs into complete and empty graphs ⋮ Partitioning cographs into cliques and stable sets ⋮ Bisplit graphs ⋮ Partial complementation of graphs ⋮ Excluding a Substar and an Antisubstar ⋮ Almost All Friendly Matrices Have Many Obstructions ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results ⋮ Point determining digraphs, $\{ 0,1 \}$-matrix partitions, and dualities in full homomorphisms ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ Partitions and well-coveredness: the graph sandwich problem ⋮ List matrix partitions of chordal graphs ⋮ $(p,k)$-coloring problems in line graphs

This page was built for publication: List Partitions