The structure of bi-arc trees
From MaRDI portal
Publication:864126
DOI10.1016/j.disc.2005.09.031zbMath1110.05093MaRDI QIDQ864126
Jing Huang, Tomás Feder, Pavol Hell
Publication date: 13 February 2007
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2005.09.031
circular arc graph; majority function; forbidden subgraph characterization; list homomorphism; bi-arc graph
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- List homomorphisms to reflexive graphs
- Graph homomorphisms and phase transitions
- Gibbs measures and dismantlable graphs
- List homomorphisms and circular arc graphs
- Representation of a finite graph by a set of intervals on the real line
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Bi‐arc graphs and the complexity of list homomorphisms