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