×

\(H\)-absorbence and \(H\)-independence in 3-quasi-transitive \(H\)-coloured digraphs. (English) Zbl 1462.05157

Summary: 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Arpin and V. Linek,Reachability problems in edge-coloured digraphs, Discrete Math. 307(2007), 2276-2289.
[2] N. Sauer B. Sands and R. Woodrow,On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B33(1982), 271-275. · Zbl 0488.05036
[3] J. Bang-Jensen and G. Gutin,Digraphs:Theory, algorithms and applications, Springer, London, 2001. · Zbl 0958.05002
[4] J. M. Le Bars,Counterexample of the 0-1 law for fragments of existential second-order logic; an overview, Bull. Symbolic Logic9(2000), 67-82. · Zbl 0958.03022
[5] C. Berge,Graphs, North-Holland, Amsterdam, 1985. · Zbl 0565.05030
[6] C. Berge and P. Duchet,Recent problems and results about kernels in directed graphs, Discrete Math.86(1990), 27-31. · Zbl 0721.05027
[7] E. Boros and V. Gurvich,Perfect graphs, kernels and cores of cooperative games, Discrete Math.306(2006), 2336-2354. · Zbl 1103.05034
[8] P. Delgado-Escalante and H. Galeana-S´anchez,Restricted domination in arc-coloured digraphs, AKCE Int. J. of Graphs Comb.11(2014), no. 1, 95-104. · Zbl 1301.05147
[9] P. Duchet,Kernels in directed graphs: a poison game, Discrete Math.115(1993), 273-276. · Zbl 0773.05052
[10] A. S. Fraenkel,Combinatorial game theory foundations applied to digraph kernels, E-JC4(1997), 17. · Zbl 0884.05045
[11] V. Linek and B. Sands,A note on paths in edge-coloured tournaments, Ars Combin. 44(1996), 225-228. · Zbl 0889.05049
[12] W. Lochet N. Bousquet and S. Thomass´e,A proof of the Erd˝os-Sans-Sauer-Woodrow conjecture, J. Combin. Theory Ser. B.137(2019), 316-319 · Zbl 1415.05061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.