List matrix partitions of chordal graphs

DOI10.1016/j.tcs.2005.09.030zbMath1084.05026OpenAlexW2114968511MaRDI QIDQ817772

Tomás Feder, Fábio Protti, Pavol Hell, Sulamita Klein, Loana Tito Nogueira

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.030

zbMATH Keywords

chordal graphsdichotomyforbidden subgraph characterizationslist homomorphismslist-colouringsmatrix partitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (30)

Matrix partitions of split graphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Obstructions to partitions of chordal graphs ⋮ On the thinness and proper thinness of a graph ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ 2K2 vertex-set partition into nonempty parts ⋮ On the complexity of coloring ‐graphs ⋮ On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs ⋮ List homomorphism: beyond the known boundaries ⋮ Matrix partitions of perfect graphs ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ Colouring, constraint satisfaction, and complexity ⋮ List matrix partitions of graphs representing geometric configurations ⋮ 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 ⋮ Unnamed Item ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Graph partitions with prescribed patterns ⋮ The complexity of list edge-partitions for simple graphs ⋮ Join colourings of chordal graphs ⋮ On Injective Colourings of Chordal Graphs ⋮ On 2-Subcolourings of Chordal Graphs ⋮ Almost All Friendly Matrices Have Many Obstructions ⋮ Minimal obstructions for a matrix partition problem in chordal graphs ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ Partitions and well-coveredness: the graph sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packing \(r\)-cliques in weighted chordal graphs
• Digraph matrix partitions and trigraph homomorphisms
• Decomposition by clique separators
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Star-cutsets and perfect graphs
• An algorithm for finding clique cut-sets
• Coloring graphs with stable cutsets
• Partitioning chordal graphs into independent sets and cliques
• Partitions of graphs into one or two independent sets and cliques
• List homomorphisms and circular arc graphs
• Complexity of graph partition problems
• List Partitions
• Bi‐arc graphs and the complexity of list homomorphisms
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Full Constraint Satisfaction Problems
• LATIN 2004: Theoretical Informatics

This page was built for publication: List matrix partitions of chordal graphs