Rainbow Connection for Complete Multipartite Graphs

MaRDI QIDQ6414741zbMATH OpenFDO

Authors Igor Araujo, Kareem Benaissa, Richard Bi, Sean English, Shengan Wu, Pai Zheng

Publication date 21 October 2022

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Abstract: A path in an edge-colored graph is said to be rainbow if no color repeats on it. An edge-colored graph is said to be rainbow $k$-connected if every pair of vertices is connected by $k$ internally disjoint rainbow paths. The rainbow $k$-connection number $mathrm{rc}_k(G)$ is the minimum number of colors $ell$ such that there exists a coloring with $ell$ colors that makes $G$ rainbow $k$-connected. Let $f(k,t)$ be the minimum integer such that every $t$-partite graph with part sizes at least $f(k,t)$ has $mathrm{rc}_k(G)le4$ if $t=2$ and $mathrm{rc}_k(G)le3$ if $tge3$. Answering a question of Fujita, Liu and Magnant, we show that [ f(k,t) = leftlceil frac{2k}{t-1} ight ceil ] for all $kgeq2$, $tgeq2$. We also give some conditions for which $mathrm{rc}_k(G)le3$ if $t=2$ and $mathrm{rc}_k(G)le2$ if $tge3$.

This page was built for publication: Rainbow Connection for Complete Multipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414741)