Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs

Let ${\overrightarrow{K}}_{\mathbb{N}}$ be the complete symmetric digraph on the positive integers. Answering a question of DeBiasio and McKenney, we construct a 2-colouring of the edges of ${\overrightarrow{K}}_{\mathbb{N}}$ in which every monochromatic path has density 0.However, if we restrict the length of monochromatic paths in one colour, then no example as above can exist: We show that every $(r+1)$-edge-coloured complete symmetric digraph (of arbitrary infinite cardinality) containing no directed paths of edge-length ${?}_i$ for any colour $i\le r$ can be covered by ${\prod }_{i\in \left[r\right]}{?}_i$ pairwise disjoint monochromatic complete symmetric digraphs in colour $r+1$.Furthermore, we present a stability version for the countable case of the latter result: We prove that the edge-colouring is uniquely determined on a large subgraph, as soon as the upper density of monochromatic paths in colour $r+1$ is bounded by ${\prod }_{i\in \left[r\right]}\frac{1}{{?}_i}$.     

On kernels by monochromatic paths in the corona of digraphs

In this paper we derive necessary and sufficient conditions for the existence of kernels by monochromatic paths in the corona of digraphs. Using these results, we are able to prove the main result of this paper which provides necessary and sufficient conditions for the corona of digraphs to be monochromatic kernel-perfect. Moreover we calculate the total numbers of kernels by monochromatic paths, independent by monochromatic paths sets and dominating by monochromatic paths sets in this digraphs product.      

Decompositions of edge-coloured infinite complete graphs into monochromatic paths II

We prove that given an edge colouring of an infinite complete graph with finitely many colours, one can partition the vertices of the graph into disjoint monochromatic paths of different colours. This answers a question of R. Rado from 1978.     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. 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 every vertex x∈(V(D)?N), there is a vertex y∈N such that there is an xy-monochromatic directed path. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

On cycles and paths in digraphs

The purpose of this communication is to announce some sufficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].     

Partitioning edge-coloured complete graphs into monochromatic cycles

A conjecture of Erdös, Gyárfás, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for $r=2$. In this note we show that in fact this conjecture is false for all $r⩾3$. We also discuss some weakenings of this conjecture which may still be true.     

Longest paths in digraphs

In this paper, we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of given length, and we characterize the extremal graphs.     

On extremal weighted digraphs with no heavy paths

Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.     

Disjoint paths in symmetric digraphs

Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration.     

Longest paths in bipartite digraphs

In this paper we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of length greater than or equal to a given value, when the digraph is bipartite and when the digraph is dipartite and oriented. These conditions are shown to be best possible.     

Covering digraphs by paths

The problems of minimum edge and minimum vertex covers by paths are discussed. The results relate to papers by Gallai-Milgram, Meyniel, Alspach-Pullman and others. One of the main results is concerned with partially ordered sets.     

Infinite Hamiltonian paths in Cayley digraphs

Let Cay(S:H) be the Cayley digraph of the generators S in the group H. A one-way infinite Hamiltonian path in the digraph G is a listing of all the vertices [ν_i:1⩽i<∞], such that there is an arc from ν_i to ν₁₊₁. A two-way infinite Hamiltonian path is similarly defined, with i ranging from −∞ to ∞. In this paper, we give conditions on S and H for the existence of one- and two-way infinite Hamiltonian paths in Cay(X:H). Two of our results can be summarized as follows. First, if S is countably infinite and H is abelian, then Cay(S:H) has one- and two-way Hamiltonian paths if and only if it is strongly connected (except for one infinite family). We also give necessary and sufficient conditions on S for Cay(S:H) to be strongly connected for a large class of Cayley digraphs. Second, we show that any Cayley digraph of a countable locally finite group has both one- and two-way infinite Hamiltonian paths. As a lemma, we give a relation between the strong connectivity and the outer valence of finite vertex-transitive digraphs.     

Antidirected paths in 5-chromatic digraphs

Let $T_5$ be the regular 5-tournament. B. Grünbaum proved that $T_5$ is the only 5-tournament which contains no copy of the antidirected path $P_4$. In this Note, we prove that, except for $T_5$, any connected 5-chromatic oriented digraph in which each vertex has out-degree at least two contains a copy of $P_4$. It will be shown, by an example, that the condition that each vertex has out-degree at least two is indispensable. To cite this article: A. El Sahili, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Kernels by properly colored paths in arc-colored digraphs

A kernel by properly colored paths of an arc-colored digraph $D$ is a set $S$ of vertices of $D$ such that (i) no two vertices of $S$ are connected by a properly colored directed path in $D$, and (ii) every vertex outside $S$ can reach $S$ by a properly colored directed path in $D$. In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given.