کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649065 | 1632448 | 2007 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The structure of bi-arc trees The structure of bi-arc trees](/preview/png/4649065.png)
Bi-arc graphs generalize (reflexive) interval graphs and those (irreflexive) bipartite graphs whose complements are circular arc graphs. They are relevant for the so-called list homomorphism problem: when H is a bi-arc graph, the problem is polynomial time solvable, otherwise it is NP-complete. Bi-arc graphs have a forbidden structure characterization, and can be recognized in polynomial time. More importantly for this paper, bi-arc graphs can be characterized by the existence of a conservative majority function. (This function plays an important role in proving the correctness of a polynomial time list homomorphism algorithm.)The forbidden structure theorem for bi-arc graphs is quite complex, and the existence of a conservative majority function is proved without giving an explicit description of it.In this note we focus on bi-arc graphs that are trees (with loops allowed). We describe the structure of bi-arc trees, and give a simple forbidden subtree characterization. Based on this structure theorem, we are able to explicitly describe the conservative majority functions.
Journal: Discrete Mathematics - Volume 307, Issues 3–5, 6 February 2007, Pages 393–401