Obstructions to partitions of chordal graphs

DOI10.1016/j.disc.2012.05.023zbMath1277.05137OpenAlexW2065396130MaRDI QIDQ383740

Pavol Hell, Shekoofeh Nekooei Rizi, Tomás Feder

Publication date: 6 December 2013

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

Full work available at URL: https://doi.org/10.1016/j.disc.2012.05.023

zbMATH Keywords

perfect graphsgraph homomorphismschordal graphsforbidden subgraph characterizationsgraph partitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Matrix partitions of split graphs ⋮ Graph partitions with prescribed patterns ⋮ Join colourings of chordal graphs ⋮ Minimal obstructions for a matrix partition problem in chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• List matrix partitions of chordal graphs
• Digraph matrix partitions and trigraph homomorphisms
• Matrix partitions with finitely many obstructions
• Decomposition by clique separators
• Star-cutsets and perfect graphs
• Partitioning chordal graphs into independent sets and cliques
• On digraph coloring problems and treewidth duality
• Matrix partitions of perfect graphs
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Algorithms for Partition of Some Class of Graphs under Compaction
• The Complexity of the List Partition Problem for Graphs
• Homomorphism preservation theorems
• 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
• Fast Skew Partition Recognition
• Bounded Tree-Width and CSP-Related Problems
• Full Constraint Satisfaction Problems
• Induced subgraphs and well‐quasi‐ordering

This page was built for publication: Obstructions to partitions of chordal graphs