Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.disc.2005.09.031 | Discrete Mathematics |
Keywords | Field | DocType |
list homomorphism,circular arc graph,homomorphism,majority function,forbidden subgraph characterization,bi-arc graph,bi-arc tree,polynomial time,bipartite graph,interval graph | Discrete mathematics,Indifference graph,Combinatorics,Forbidden graph characterization,Robertson–Seymour theorem,Chordal graph,Cograph,Pathwidth,1-planar graph,Mathematics,Strong perfect graph theorem | Journal |
Volume | Issue | ISSN |
307 | 3-5 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomás Feder | 1 | 1959 | 184.99 |
| Pavol Hell | 2 | 2638 | 288.75 |
| Jing Huang | 3 | 2464 | 186.09 |