Transversals in a collection of graphs with degree conditions

-- Luyi Li (LISN, Galac)

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 with V()=V and E() 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.

Category: seminars
Tags: Team seminar graphs