Graph partitions with prescribed patterns
From MaRDI portal
Publication:2509761
Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
Cites work
- \(2K_{2}\) vertex-set partition into nonempty parts
- A Characterisation of First-Order Constraint Satisfaction Problems
- A new proof of the \(H\)-coloring dichotomy
- About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
- Absolute Retracts and Varieties of Reflexive Graphs
- Algorithms for partition of some class of graphs under compaction
- An algorithm for finding clique cut-sets
- Berge trigraphs
- Bisplit graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Colouring, constraint satisfaction, and complexity
- Colourings, homomorphisms, and partitions of transitive digraphs
- Complexity of tree homomorphisms
- Computational Complexity of Compaction to Reflexive Cycles
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Covering graphs with few complete bipartite subgraphs
- CSP dichotomy for special triads
- Decomposition by clique separators
- Dichotomy for tree-structured trigraph list homomorphism problems
- Digraph matrix partitions and trigraph homomorphisms
- Dualities for Constraint Satisfaction Problems
- Dualities in full homomorphisms
- Duality and Polynomial Testing of Tree Homomorphisms
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Extension problems with degree bounds
- Fast Skew Partition Recognition
- FindingH-partitions efficiently
- Full Constraint Satisfaction Problems
- Generalized colouring (matrix partitions) of cographs
- Graph Theory and Probability
- Hereditarily hard \(H\)-colouring problems
- Homomorphism preservation theorems
- Homomorphisms to oriented paths
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1161313 (Why is no real title available?)
- scientific article; zbMATH DE number 1996252 (Why is no real title available?)
- scientific article; zbMATH DE number 1545651 (Why is no real title available?)
- scientific article; zbMATH DE number 2151253 (Why is no real title available?)
- scientific article; zbMATH DE number 2159638 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 878894 (Why is no real title available?)
- Induced subgraphs and well‐quasi‐ordering
- Linear time solvable optimization problems on graphs of bounded clique-width
- List homomorphisms and circular arc graphs
- List homomorphisms of graphs with bounded degrees
- List homomorphisms to reflexive graphs
- List matrix partitions of chordal graphs
- List Partitions
- Matrix partitions of perfect graphs
- Matrix partitions of split graphs
- Matrix partitions with finitely many obstructions
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- NP for Combinatorialists
- Obstructions to partitions of chordal graphs
- On digraph coloring problems and treewidth duality
- On disconnected cuts and separators
- On generalized split graphs
- On list coloring and list homomorphism of permutation and interval graphs
- On realizations of point determining graphs, and obstructions to full homomorphisms
- On the complexity of colouring by superdigraphs of bipartite graphs
- On the complexity of H-coloring
- Partitioning chordal graphs
- Partitioning chordal graphs into independent sets and cliques
- Partitions of graphs into one or two independent sets and cliques
- Polarity of chordal graphs
- Retractions to Pseudoforests
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Star-cutsets and perfect graphs
- The complexity of \(H\)-colouring of bounded degree graphs
- The Complexity of Colouring by Semicomplete Digraphs
- The complexity of list edge-partitions for simple graphs
- The complexity of surjective homomorphism problems-a survey
- The Complexity of the List Partition Problem for Graphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The dichotomy of list homomorphisms for digraphs
- The effect of two cycles on the complexity of colourings by directed graphs
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
- Two algorithms for general list matrix partitions
Cited in
(25)- List matrix partitions of graphs representing geometric configurations
- The monotonicity property of \(M\)-partition problems
- Minimal obstructions for a matrix partition problem in chordal graphs
- Minimal obstructions to \(( s , 1 )\)-polarity in cographs
- Complexity of correspondence \(H\)-colourings
- Disconnected cuts in claw-free graphs
- Characterization of color patterns by dynamic \(H\)-paths
- Point determining digraphs, \(\{ 0,1 \}\)-matrix partitions, and dualities in full homomorphisms
- Minimal obstructions to 2-polar cographs
- Join colourings of chordal graphs
- Matrix partitions of split graphs
- Graph partitions: recent progresses and some open problems
- Colourings, homomorphisms, and partitions of transitive digraphs
- Editing graphs into few cliques: complexity, approximation, and kernelization schemes
- scientific article; zbMATH DE number 1189243 (Why is no real title available?)
- An algebraic hardness criterion for surjective constraint satisfaction.
- Disconnected cuts in claw-free graphs
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Almost all friendly matrices have many obstructions
- Computational complexity relationship between compaction, vertex-compaction, and retraction
- On guarded extensions of MMSNP
- Full-homomorphisms to paths and cycles
- Generalisations of matrix partitions: complexity and obstructions
- On guarded extensions of MMSNP
- The complexity of list edge-partitions for simple graphs
This page was built for publication: Graph partitions with prescribed patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509761)
