BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given a tournament T, let h(T) be the smallest integer k such that every arc-coloring of T with k or more colors produces at least one out-directed spanning tree of T with no pair of arcs with the same color. In this paper we give the exact value of h(T).
An arc-coloured digraph D is said to be \emph{rainbow connected} if for every two vertices u and v there is an uv-path all whose arcs have different colours. The minimun number of colours required to make the digraph rainbow connected is called the \emph{rainbow connection number} of D, denoted rc→(D). In \cite{Dorbec} it was showed that if T is a strong tournament with n≥5 vertices, then 2≤rc→(T)≤n−1; and that for every n and k such that 3≤k≤n−1, there exists a tournament T on n vertices such that rc→(T)=k. In this note it is showed that for any n≥6, there is a tournament T of n vertices such that rc→(T)=2.
An edge-coloured graph G is {\it rainbow connected} if any two vertices are connected by a path whose edges have distinct colours. This concept was introduced by Chartrand et al. in \cite{ch01}, and it was extended to oriented graphs by Dorbec et al. in \cite{DI}. In this paper we present some results regarding this extention, mostly for the case of circulant digraphs.
An m-colored digraph D has k-colored kernel if there exists a subset K of its vertices such that for every vertex v∈/K there exists an at most k-colored directed path from v to a vertex of K and for every there does not exist an at most k-colored directed path between them. In this paper we prove that an m-colored semicomplete r-partite digraph D has a k-colored kernel provided that r≥3 and {enumerate} [(i)] k≥4, [(ii)] k=3 and every C4 contained in D is at most 2-colored and, either every C5 contained in D is at most 3-colored or every C3↑C3 contained in D is at most 2-colored, [(iii)] k=2 and every C3 and C contained in D is monochromatic. {enumerate} If D is an m-colored semicomplete bipartite digraph and k=2 (resp. k=3) and every C4⇈C4 contained in D is at most 2-colored (resp. 3-colored), then D has a -colored (resp. 3-colored) kernel. Using these and previous results, we obtain conditions for the existence of k-colored kernels in m-colored semicomplete r-partite digraphs for every k≥2 and r≥2.
We study k-colored kernels in m-colored digraphs. An m-colored digraph D has k-colored kernel if there exists a subset K of its vertices such that (i) from every vertex v∈/K there exists an at most k-colored directed path from v to a vertex of K and (ii) for every u,v∈K there does not exist an at most k-colored directed path between them. In this paper, we prove that for every integer k≥2 there exists a -colored digraph D without k-colored kernel and if every directed cycle of an m-colored digraph is monochromatic, then it has a k-colored kernel for every positive integer k. We obtain the following results for some generalizations of tournaments: (i) m-colored quasi-transitive and 3-quasi-transitive digraphs have a k% -colored kernel for every k≥3 and k≥4, respectively (we conjecture that every m-colored l-quasi-transitive digraph has a k% -colored kernel for every k≥l+1), and (ii) m-colored locally in-tournament (out-tournament, respectively) digraphs have a k-colored kernel provided that every arc belongs to a directed cycle and every directed cycle is at most k-colored.
The heterochromatic number hc(H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by nu(H) the number of vertices of H and by tau(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n > 2 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then hc(H) = nu(H) - tau(H) + 2. We also show that hc(H) = nu(H) - tau(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.