Graph partitions with prescribed patterns

DOI10.1016/j.ejc.2013.06.043zbMath1292.05214OpenAlexW1963693997MaRDI QIDQ2509761

Pavol Hell

Publication date: 29 July 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2013.06.043

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (21)

Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ Matrix partitions of split graphs ⋮ Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Minimal obstructions to 2-polar cographs ⋮ Minimal obstructions to \(( s , 1 )\)-polarity in cographs ⋮ Complexity of correspondence \(H\)-colourings ⋮ Disconnected cuts in claw-free graphs ⋮ On guarded extensions of MMSNP ⋮ Full-homomorphisms to paths and cycles ⋮ Unnamed Item ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ List matrix partitions of graphs representing geometric configurations ⋮ The monotonicity property of \(M\)-partition problems ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ The complexity of list edge-partitions for simple graphs ⋮ Join colourings of chordal graphs ⋮ Characterization of color patterns by dynamic \(H\)-paths ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ Almost All Friendly Matrices Have Many Obstructions ⋮ Minimal obstructions for a matrix partition problem in chordal graphs ⋮ Point determining digraphs, \(\{ 0,1 \}\)-matrix partitions, and dualities in full homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colourings, homomorphisms, and partitions of transitive digraphs
• Obstructions to partitions of chordal graphs
• The complexity of surjective homomorphism problems-a survey
• Colouring, constraint satisfaction, and complexity
• On the complexity of colouring by superdigraphs of bipartite graphs
• The complexity of list edge-partitions for simple graphs
• List matrix partitions of chordal graphs
• Digraph matrix partitions and trigraph homomorphisms
• List homomorphisms of graphs with bounded degrees
• The effect of two cycles on the complexity of colourings by directed graphs
• Polarity of chordal graphs
• \(2K_{2}\) vertex-set partition into nonempty parts
• Matrix partitions with finitely many obstructions
• Covering graphs with few complete bipartite subgraphs
• Extension problems with degree bounds
• Dualities in full homomorphisms
• Decomposition by clique separators
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• On the complexity of H-coloring
• Star-cutsets and perfect graphs
• List homomorphisms to reflexive graphs
• An algorithm for finding clique cut-sets
• Homomorphisms to oriented paths
• The complexity of \(H\)-colouring of bounded degree graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Partitioning chordal graphs into independent sets and cliques
• Hereditarily hard \(H\)-colouring problems
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Partitions of graphs into one or two independent sets and cliques
• Complexity of tree homomorphisms
• Linear time solvable optimization problems on graphs of bounded clique-width
• List homomorphisms and circular arc graphs
• Dichotomy for tree-structured trigraph list homomorphism problems
• On disconnected cuts and separators
• On digraph coloring problems and treewidth duality
• Matrix partitions of perfect graphs
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Bisplit graphs
• Matrix partitions of split graphs
• Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
• Absolute Retracts and Varieties of Reflexive Graphs
• A New Proof of the H-Coloring Dichotomy
• Retractions to Pseudoforests
• Algorithms for Partition of Some Class of Graphs under Compaction
• Graph Theory and Probability
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• CSP dichotomy for special triads
• NP for Combinatorialists
• The Complexity of the List Partition Problem for Graphs
• Homomorphism preservation theorems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Complexity of Colouring by Semicomplete Digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Bi‐arc graphs and the complexity of list homomorphisms
• Duality and Polynomial Testing of Tree Homomorphisms
• On List Coloring and List Homomorphism of Permutation and Interval Graphs
• Fast Skew Partition Recognition
• A Characterisation of First-Order Constraint Satisfaction Problems
• Full Constraint Satisfaction Problems
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Berge trigraphs
• Dualities for Constraint Satisfaction Problems
• Induced subgraphs and well‐quasi‐ordering

This page was built for publication: Graph partitions with prescribed patterns