Polychromatic edge-colorings of subgraphs of balanced complete bipartite graphs
Xia Zhang, Jiang Zhenzhen, Zhang Xinmiao · Scientia Sinica Mathematica · 2024
Let G be a graph and mathcalWbe a set of some subgraphs of G. An m-edge-coloring of G is called mathcalW-polychromatic if every subgraph isomorphic to some element from mathcalWreceives all m colors. In this paper, the close relationship between the subgraph polychromatic edge-coloring problem of graphs and the Turán problem is uncovered, and the mathcalW-polychromatic edge-coloring problem of the complete bipartite graph K_n,nis studied. We determine the exact value of the mathcalW-polychomatic number to be n+1, n+1, ⌊ fracn^23