List matrix partitions of graphs representing geometric configurations

DOI10.1016/j.dam.2019.01.013zbMath1409.05165OpenAlexW2912875731WikidataQ128359601 ScholiaQ128359601MaRDI QIDQ1741515

Payam Valadkhan

Publication date: 3 May 2019

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

Full work available at URL: https://doi.org/10.1016/j.dam.2019.01.013

zbMATH Keywords

interval graphspermutation graphsspecial graph classesgraph partitionscircular arc graphslist $M$-partition problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

List homomorphism: beyond the known boundaries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List matrix partitions of chordal graphs
• The complexity of comparability graph recognition and coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Modular decomposition and transitive orientation
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Linear-time recognition of circular-arc graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Graph partitions with prescribed patterns
• Matrix partitions of split graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Graph Classes: A Survey
• List Partitions
• On List Coloring and List Homomorphism of Permutation and Interval Graphs

This page was built for publication: List matrix partitions of graphs representing geometric configurations