Transversals in a collection of graphs with degree conditions
Time: 14:00 -- Location: LRI, 445
summary: Let G={G_1, G_2, ... , G_m} be a collection of n-vertex graphs on the same vertex set V (a graph system),
and F be a simple graph with e(F) ≤ m. If there is an injection f: E(F) → [m] such that e &isinv E(G_{f(e)}) for each e &isinv E(F),
then F is a partial transversal of G. If moreover e(F)=m, then it is a transversal of G.
From another perspective, we can see G as an edge-colored multigraph G̃ with V(G̃)=V
and E(G̃) a multiset consisting of E(G_1), ... , E(G_m), and each edge e of G̃ is colored by i if e &isinv E(G_i).
Since all edges of F belong to distinct graphs of G, we also call F a rainbow subgraph of G.
We say that G is rainbow vertex-pancyclic if G contains a rainbow cycle of length ℓ for each
ℓ &isinv [3, n], and G is rainbow vertex-pancyclic if each vertex of V is contained in a rainbow cycle of G
with length ℓ for every integer ℓ &isinv [3, n].
In this talk, we study the rainbow pancyclicity of a collection of graphs and vertex-even-pancyclicity of a collection of bipartite graphs.
Moreover, we study rainbow Hamiltonicity of a collection of digraphs.
This is joint work with Jie Hu, Hao Li, Ping Li, Xueliang Li and Ningyan Xu.