List matrix partitions of chordal graphs
DOI10.1016/J.TCS.2005.09.030zbMATH Open1084.05026OpenAlexW2114968511MaRDI QIDQ817772FDOQ817772
Authors: Tomás Feder, Pavol Hell, Sulamita Klein, Loana T. Nogueira, Fábio Protti 
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
Recommendations
chordal graphsdichotomyforbidden subgraph characterizationslist homomorphismslist-colouringsmatrix partitions
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Decomposition by clique separators
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Full Constraint Satisfaction Problems
- Title not available (Why is that?)
- Partitioning chordal graphs into independent sets and cliques
- Partitions of graphs into one or two independent sets and cliques
- Complexity of graph partition problems
- List Partitions
- Digraph matrix partitions and trigraph homomorphisms
- Star-cutsets and perfect graphs
- List homomorphisms and circular arc graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Title not available (Why is that?)
- An algorithm for finding clique cut-sets
- Two algorithms for general list matrix partitions
- The list partition problem for graphs
- Coloring graphs with stable cutsets
- Title not available (Why is that?)
- LATIN 2004: Theoretical Informatics
- Packing \(r\)-cliques in weighted chordal graphs
Cited In (35)
- On the complexity of coloring ‐graphs
- Matrix partitions of perfect graphs
- Partitions and well-coveredness: the graph sandwich problem
- On realizations of point determining graphs, and obstructions to full homomorphisms
- Graph partitions with prescribed patterns
- Join colourings of chordal graphs
- Title not available (Why is that?)
- List matrix partitions of graphs representing geometric configurations
- Colouring, constraint satisfaction, and complexity
- On the probe problem for \((r,\ell )\)-well-coveredness
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- Matrix Partitions with Finitely Many Obstructions
- The complexity of list edge-partitions for simple graphs
- On 2-Subcolourings of Chordal Graphs
- Well-partitioned chordal graphs
- The external constraint 4 nonempty part sandwich problem
- On the thinness and proper thinness of a graph
- Polarity of chordal graphs
- \(2K_{2}\) vertex-set partition into nonempty parts
- Counting List Matrix Partitions of Graphs
- Almost all friendly matrices have many obstructions
- Dichotomy for tree-structured trigraph list homomorphism problems
- Partitioning chordal graphs into independent sets and cliques
- Digraph matrix partitions and trigraph homomorphisms
- 2K2 vertex-set partition into nonempty parts
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- Matrix partitions of split graphs
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- Chordal multipartite graphs and chordal colorings
- Obstructions to partitions of chordal graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- LATIN 2004: Theoretical Informatics
- Minimal obstructions for a matrix partition problem in chordal graphs
- On Injective Colourings of Chordal Graphs
- List homomorphism: beyond the known boundaries
This page was built for publication: List matrix partitions of chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817772)
