H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs.


  • Hortensia Galeana-Sanchez Instituto de Matematicas, UNAM
  • Eugenia O'Reilly-Regueiro Instituto de Matematicas, UNAM




In this paper we prove that if $D$ is a loopless asymmetric 3-quasi-transitive arc-coloured digraph having its arcs coloured with the vertices of a given digraph $H$, and if in $D$ every $C_4$ is an $H$-cycle and every $C_3$ is a quasi-$H$-cycle, then $D$ has an $H$-kernel.



\bibitem{A-L} P. Arpin and V. Linek, {\it Reachability problems in edge-coloured digraphs}, Discrete Math. {\bf 307} (2007), 2276-2289.

\bibitem{B-J-G}J. Bang-Jensen, G. Gutin, {\it Digraphs: Theory, Algorithms and Applications}, Springer, London, 2001.

\bibitem{B}C. Berge, {\it Graphs}, North-Holland, Amsterdam, 1985.

\bibitem{B-D}C. Berge and P. Duchet, {\it Recent problems and results about kernels in directed graphs}, Discrete Math. {\bf 86} (1990), 27--31.

\bibitem{L-B1} J. M. Le Bars, {\it Counterexample of the 0-1 law for

fragments of existential second-order logic; an overview}, Bull. Symbolic

Logic, {\bf 9} (2000), 67--82.

\bibitem{L-B2} J. M. Le Bars, {\it The 0-1 law fails for frame

satisfiability of propositional model logic, in:} Proceedings of the 17th

Symposium on Logic in Computer Science, (2002), 225--234.

\bibitem{B-G} E. Boros and V. Gurvich, {\it Perfect graphs, kernels and

cores of cooperative games}, Discrete Math., {\bf 306} (2006),


\bibitem{D-G} P. Delgado-Escalante and H. Galeana-S\'anchez, {\it Restricted domination in arc-coloured digraphs}.

\bibitem{D3} P. Duchet, Kernels in directed graphs: a poison game, {\it Discrete Math.}, {\bf 115} (1993), 273-276.

\bibitem{F1} A. S. Fraenkel, {\it Combinatorial game theory foundations

applied to digraph kernels}, The Electronic Journal of Combinatorics,

{\bf 4} (1997), 17.

\bibitem{F2} A. S. Fraenkel, {\it Combinatorial games: selected

bibliography with a succinct gourmet introduction}, The Electronic Journal of Combinatorics, {\bf 14} (2007), \#DS2.

\bibitem{H-H-S1} T. W. Haynes, T. Hedetniemi and P. J. Slater, editors, {\it

Domination in Graphs, Advanced Topics}, Marcel Dekker Inc., (1998).

\bibitem{H-H-S2} T. W. Haynes, T. Hedetniemi and P. J. Slater, editors, {\it

Fundamentals of Domination in Graphs}, Marcel Dekker Inc., (1998).

\bibitem{L-S} V. Linek and B. Sands, {\it A note on paths in edge-coloured tournaments}, Ars Combin. {\bf 44} (1996), 225-228.