Matrix partitions of perfect graphs

DOI10.1016/j.disc.2005.12.035zbMath1143.05035OpenAlexW2079295608MaRDI QIDQ2433706

Tomás Feder, Pavol Hell

Publication date: 30 October 2006

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

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

zbMATH Keywords

polynomial time algorithmperfect graphsdichotomyNP-complete problemforbidden subgraph characterizationmatrix partition\(M\)-partitiontrigraph homomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items (20)

Partitioning permutations into monotone subsequences ⋮ Matrix partitions of split graphs ⋮ Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Obstructions to partitions of chordal graphs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ 2K2 vertex-set partition into nonempty parts ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Partitioning extended \(P_4\)-laden graphs into cliques and stable sets ⋮ Colouring, constraint satisfaction, and complexity ⋮ The monotonicity property of \(M\)-partition problems ⋮ Polarity of chordal graphs ⋮ On realizations of point determining graphs, and obstructions to full homomorphisms ⋮ The external constraint 4 nonempty part sandwich problem ⋮ \(2K_{2}\) vertex-set partition into nonempty parts ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Graph partitions with prescribed patterns ⋮ The complexity of list edge-partitions for simple graphs ⋮ Join colourings of chordal graphs ⋮ Matrix Partitions with Finitely Many Obstructions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List matrix partitions of chordal graphs
• Decomposition by clique separators
• On the complexity of H-coloring
• Star-cutsets and perfect graphs
• An algorithm for finding clique cut-sets
• Partitioning chordal graphs into independent sets and cliques
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Normal hypergraphs and the perfect graph conjecture
• Point determination in graphs
• On the Structure of Polynomial Time Reducibility
• List Partitions
• Full Constraint Satisfaction Problems

This page was built for publication: Matrix partitions of perfect graphs