Displaying similar documents to “Monochromatic paths and quasi-monochromatic cycles in edge-coloured bipartite tournaments”

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs

Enrique Casas-Bautista, Hortensia Galeana-Sánchez, Rocío Rojas-Monroy (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A γ-cycle in D is a sequence of vertices, say γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ 0, 1, . . . , n there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the...

γ-Cycles In Arc-Colored Digraphs

Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, Rocío Rojas-Monroy (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and for every...

Kernels and cycles' subdivisions in arc-colored tournaments

Pietra Delgado-Escalante, Hortensia Galeana-Sánchez (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there...

Kernels in monochromatic path digraphs

Hortensia Galeana-Sánchez, Laura Pastrana Ramírez, Hugo Alberto Rincón Mejía (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈...

Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured...

Kernels in edge coloured line digraph

H. Galeana-Sánchez, L. Pastrana Ramírez (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed path between them and (ii) for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an...

Monochromatic paths and monochromatic sets of arcs in bipartite tournaments

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours and all of them are used. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices there is no monochromatic path between them and for every vertex v in V(D)∖N there is a monochromatic path from v to some vertex in N. We denote by A⁺(u) the set of arcs of D that have u as...

Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. We call the digraph D an m-coloured digraph if each arc of D is coloured by an element of {1,2,...,m} where m ≥ 1. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if there is no monochromatic path between two vertices of N and if for every vertex v not in N there is a monochromatic path from v...

Exponents of two-colored digraphs

Yan Ling Shao, Yubin Gao (2009)

Czechoslovak Mathematical Journal

Similarity:

We consider the primitive two-colored digraphs whose uncolored digraph has n + s vertices and consists of one n -cycle and one ( n - 3 ) -cycle. We give bounds on the exponents and characterizations of extremal two-colored digraphs.

On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

Pietra Delgado-Escalante, Hortensia Galeana-Sánchez (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...

Monochromatic cycles and monochromatic paths in arc-colored digraphs

Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, Rocío Rojas-Monroy (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different...

Kernels by monochromatic paths and the color-class digraph

Hortensia Galeana-Sánchez (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of...

Some Remarks On The Structure Of Strong K-Transitive Digraphs

César Hernández-Cruz, Juan José Montellano-Ballesteros (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least...

Independent Detour Transversals in 3-Deficient Digraphs

Susan van Aardt, Marietjie Frick, Joy Singleton (2013)

Discussiones Mathematicae Graph Theory

Similarity:

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph...

Kernels by Monochromatic Paths and Color-Perfect Digraphs

Hortensia Galeana-Śanchez, Rocío Sánchez-López (2016)

Discussiones Mathematicae Graph Theory

Similarity:

For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different...

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

Pavol Hell, César Hernández-Cruz (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in...