Obstructions to partitions of chordal graphs

DOI10.1016/J.DISC.2012.05.023zbMATH Open1277.05137OpenAlexW2065396130MaRDI QIDQ383740FDOQ383740

Authors: Tomás Feder, Pavol Hell, Shekoofeh Nekooei Rizi 

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

Recommendations

• Partitioning chordal graphs
• List matrix partitions of chordal graphs
• Minimal obstructions for a matrix partition problem in chordal graphs
• LATIN 2004: Theoretical Informatics
• Matrix partitions of perfect graphs

zbMATH Keywords

graph homomorphismschordal graphsperfect graphsforbidden subgraph characterizationsgraph partitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Decomposition by clique separators
• Title not available (Why is that?)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Colouring, constraint satisfaction, and complexity
• Full Constraint Satisfaction Problems
• Partitioning chordal graphs into independent sets and cliques
• The Complexity of the List Partition Problem for Graphs
• The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
• On digraph coloring problems and treewidth duality
• List Partitions
• Matrix partitions of perfect graphs
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Digraph matrix partitions and trigraph homomorphisms
• Star-cutsets and perfect graphs
• Fast Skew Partition Recognition
• Bounded Tree-Width and CSP-Related Problems
• Homomorphism preservation theorems
• Matrix partitions with finitely many obstructions
• Partitioning chordal graphs
• Algorithms for partition of some class of graphs under compaction
• Title not available (Why is that?)
• Title not available (Why is that?)
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Induced subgraphs and well‐quasi‐ordering
• List matrix partitions of chordal graphs

Cited In (14)

• Matrix partitions with finitely many obstructions
• Matrix partitions of perfect graphs
• Graph partitions with prescribed patterns
• Join colourings of chordal graphs
• The monotonicity property of \(M\)-partition problems
• Matrix Partitions with Finitely Many Obstructions
• Title not available (Why is that?)
• Almost all friendly matrices have many obstructions
• Generalized colouring (matrix partitions) of cographs
• Matrix partitions of split graphs
• Bad News for Chordal Partitions
• Obstructions to a general characterization of graph correspondences
• Minimal obstructions for a matrix partition problem in chordal graphs
• List matrix partitions of chordal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q383740)