## k-Interval-filament graphs

### Author: Fanica Gavril

ABSTRACT
For a fixed $k$, an oriented graph is $k-transitive$ if it is acyclic and for every directed path $p=u1-> u2-> ...->uk+2$ with $k+2$ vertices, $p$ induces a clique if each of the two subpaths $u1->u2->...->uk+1$ and $u2->...->uk+2$ induces a clique. We describe an algorithm to find a maximum weight clique in a $k$-transitive graph.

Consider a hereditary family $G$ of graphs. A graph $H(V,E)$ is called $G-k-mixed$ if its edge set can be partitioned into two disjoint subsets $E1$, $E2-E3$ such that $H(V,E1) \in$G$,$H(V,E2)$is transitive,$H(V,E2-E3)$is$k$-transitive and for every three distinct vertices$u,v,w$if$u->v \in E2$and$(v,w) \in E1$then$(u,w) \in E1$. The letter$G$is generic and can be replaced by names of specific families. We show that if the family$G$has a polynomial time algorithm to find a maximum clique, then, under certain restrictions there exists a polynomial time algorithm to find a maximum clique in a family of$G-k$-mixed graphs. Let$I$be a family of intervals on a line$L$in a plane$PL$such that every two intersecting intervals have a common segment. In$PL$, above$L$, construct to each interval$i(v) \in I$a filament$v $connecting its two endpoints, such that for every two filaments$u,v$having$u \bigcap v \not = empty_set $and disjoint intervals$i(u)<i(v)$, there are no$k$filaments$w$with$i(u)<i(w)<i(v)$which intersect neither$u$nor$v$, are mutually disjoint and have mutually disjoint intervals. This is a$family of k-interval-filaments$and its intersection graph is a$k-interval-filament graph$; their complements are ($k$-transitive) mixed graphs and have a polynomial time algorithm for maximum cliques. Now, when two filaments$u,v$do not intersect because$u \subset v$, and between$u$and$v$there are at most$k-1$non-intersecting filaments$w1,...,wk-1$such that$wi \subset wi+1$and intersect neither$u$nor$v$, we attach to each one of$u,v$a branch in the space above$PL$such that the two branches intersect. This is a$ family of general-k-interval-filaments$and its intersection graph is a$general-k-interval-filament graph$; their complements are ($k$-transitive)-$k\$-mixed graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-30.pdf

DIMACS Home Page