Recognizing interval bigraphs by forbidden patterns

DOI10.1002/jgt.22792zbMath1522.05473arXiv1211.2662OpenAlexW4205629509MaRDI QIDQ6081553

Arash Rafiey

Publication date: 5 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.2662

zbMATH Keywords

interval graphsforbidden patternsinterval bigraphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ On the kernel and related problems in interval digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Bipartite permutation graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Approximation of Minimum Cost Homomorphisms
• Ordering without Forbidden Patterns
• The LBFS Structure and Recognition of Interval Graphs
• Interval digraphs: An analogue of interval graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Interval bigraphs and circular arc graphs
• On the computational complexity of ordered subgraph recognition

This page was built for publication: Recognizing interval bigraphs by forbidden patterns