TITLE

ON MONOCHROMATIC PATHS AND BICOLORED SUBDIGRAPHS IN ARC-COLORED TOURNAMENTS

AUTHOR(S)
DELGADO-ESCALANTE, PIETRA; GALEANA-SANCHEZ, HORTENSIA
PUB. DATE
November 2011
SOURCE
Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 4, p791
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
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 and bicolor coloration. We also prove that our conditions are not mutually implied and that they are not implied by those known previously. Besides some open problems are proposed.
ACCESSION #
66787062

 

Related Articles

  • 3-TRANSITIVE DIGRAPHS. Hernández-Cruz, César // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p205 

    Let D be a digraph, V (D) and A(D) will denote the sets of vertices and arcs of D, respectively. A digraph D is 3-transitive if the existence of the directed path (u; v;w; x) of length 3 in D implies the existence of the arc (u, x) ∈ A(D). In this article strong 3-transitive digraphs are...

  • KERNELS BY MONOCHROMATIC PATHS AND THE COLOR-CLASS DIGRAPH. GALEANA-SÁNCHEZ, HORTENSIA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p273 

    No abstract available.

  • MONOCHROMATIC CYCLES AND MONOCHROMATIC PATHS IN ARC-COLORED DIGRAPHS. GALEANA-SÁNCHEZ, HORTENSIA; GAYTÁN-GÓMEZ, GUADALUPE; ROJAS-MONROY, ROCÍO // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p283 

    No abstract available.

  • HAMILTONIAN-COLORED POWERS OF STRONG DIGRAPHS. JOHN, GARRY; JONES, RYAN; KOLASINSKI, KYLE; ZHANG, PING // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p705 

    For a strong oriented graph D of order n and diameter d and an integer k with 1≤ k ≤ d, the kth power Dk of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of Dk if the directed distance dD(u, v) from u to v in D is at most k. For every strong digraph...

  • Game-perfect digraphs. Andres, Stephan // Mathematical Methods of Operations Research;Dec2012, Vol. 76 Issue 3, p321 

    In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The...

  • Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree. Cohen, Nathann; Havet, Fr�d�ric // Graphs & Combinatorics;Nov2011, Vol. 27 Issue 6, p831 

    A proper vertex colouring of a graph G is 2- frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2- frugally (resp. linearly) L- colourable if for a given list assignment $${L:V(G)\mapsto...

  • Acyclic 5-choosability of planar graphs without 4-cycles. Borodin, O.; Ivanova, A. // Siberian Mathematical Journal;May2011, Vol. 52 Issue 3, p411 

    The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud,...

  • A Note on Heterochromatic C in Edge-Colored Triangle-Free Graphs. Wang, Guanghui; Li, Hao; Zhu, Yan; Liu, Guizhen // Graphs & Combinatorics;Nov2012, Vol. 28 Issue 6, p901 

    Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d( v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an...

  • An Algorithm to Detect Cycle in an Undirected Graph. Kumar, Anand; Jani, N. N. // International Journal of Computational Intelligence Research;2010, Vol. 6 Issue 2, p305 

    This paper presents a novel algorithm to detect cycles in a graph. The graph may be of any type. Cycles are available in a graph and in much real life application; it is required to know the existence of cycles in a graph. This algorithm is developed in the context of network design problem but...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics