Matrix Partitions with Finitely Many Obstructions

DOI10.1016/j.endm.2007.01.057zbMath1158.05325MaRDI QIDQ3439607

Tomás Feder, Pavol Hell, Wing Xie

Publication date: 29 May 2007

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

Full work available at URL: https://doi.org/10.1016/j.endm.2007.01.057

zbMATH Keywords

forbidden subgraphs; matrix partitions; generalized colourings

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C75: Structural characterization of families of graphs

15A99: Basic linear algebra

Related Items

An asymptotically tight bound on the adaptable chromatic number, Almost All Friendly Matrices Have Many Obstructions, The adaptable choosability number grows with the choosability number, On realizations of point determining graphs, and obstructions to full homomorphisms

Cites Work

• List matrix partitions of chordal graphs
• The strong perfect graph theorem
• Digraph matrix partitions and trigraph homomorphisms
• Decomposition by clique separators
• On the complexity of H-coloring
• 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
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• FindingH-partitions efficiently
• Full Constraint Satisfaction Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item