Vertex-disjoint rainbow cycles in edge-colored graphs (Q2138972)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex-disjoint rainbow cycles in edge-colored graphs |
scientific article |
Statements
Vertex-disjoint rainbow cycles in edge-colored graphs (English)
0 references
17 May 2022
0 references
The existence of cycles, e.g. Hamiltonian cycles or cycles of a fixed length, in graphs (and directed cycles in digraphs) is a well-studied topic, containing classic results such as Dirac's theorem. Related to this, one can also wonder about sufficient conditions for a coloured graph to have a rainbow cycle, i.e. a cycle whose vertices or edges all have different colours. The authors of this paper consider a version of a problem in this direction. Let \(G\) be an edge-colored graph of order \(n\). Then there exists a smallest function \(f(n)\) such that if every pair of vertices \((u,v)\) together see at least \(f(n)\) colours, i.e. the union of their color-neighborhood is at least \(f(n)\), then the graph \(G\) necessarily contains a rainbow cycle. In this paper, it is proved that \(f(n) \le \lfloor \frac n2 \rfloor\). The analog of this problem where one is interested in having \(k\) vertex-disjoint rainbow cycles, is also considered.
0 references
edge-colored graph
0 references
color-neighborhood
0 references
vertex-disjoint cycles
0 references
rainbow cycle
0 references
0 references