<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume11 Issue1" %>
A Characterization of Mixed Branching Greedoids
Steven J. Tedford
Department of Mathematical Sciences, Franklin and Marshall College, Lancaster, PA 17604-3003, USA
Annals of Combinatorics 11 (1) p.79-100 March, 2007
AMS Subject Classification: 05B99, 05C99

Branching greedoids have been defined and characterized for both directed and undirected rooted graphs. Such greedoids can be extended to rooted mixed graphs - graphs with both directed and undirected edges. These greedoids are characterized by a list of forbidden minors.

If Ω is a rooted mixed graph, its mixed branching greedoid has the edges of Ω as its ground set and the collection of arborescences as its feasible sets. The set of mixed branching greedoids is exactly the set of local forest greedoids without

({a; b; c}; {Ø; {a}; {b}; {c}; {a; b}; {a; c}; {b; c}})

as a minor.

Keywords: greedoid, forbidden minor, rooted mixed graph


1. H. Crapo, Selectors: a theory of formal languages, semimodular lattices and shelling processes, Adv. Math. 54 (1984) 233-277.

2. B. Korte and L. Lovász, Structural properties of greedoids, Combinatorica 3 (1983) 359- 374.

3. B. Korte and L. Lovász, Shelling structures, convexity and a happy end, In: Graph Theory and Combinatorics, B. Bollobás Ed., Academic Press, London, (1984) pp. 221-243.

4. B. Korte, L. Lovász, and R. Schrader, Greedoids, Springer-Verlag, New York, 1991.

5. W. Schmidt, Strukturelle Aspekte in der kombinatorischen Optimierung: Greedoide auf Graphen, Ph.D. Thesis, Universität Bonn, 1985.

6. W. Schmidt, A characterization of undirected branching greedoids, J. Combin. Theory Ser. B 45 (1988) 160-184.

7. W. Schmidt, Greedoids and searches in directed graphs, Discrete Math. 93 (1991) 75-88.

8. S.J. Tedford, A characteristic polynomial for rooted mixed graphs, Discrete Math. 304 (2005) 121-127.