The structure of bi-arc trees

DOI10.1016/j.disc.2005.09.031zbMath1110.05093OpenAlexW1991072872MaRDI 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

zbMATH Keywords

circular arc graphmajority functionforbidden subgraph characterizationlist homomorphismbi-arc graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

List homomorphism problems for signed trees

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