Edge-colorings of K_m,n which forbid multicolored cycles

MaRDI QIDQ2848790zbMATH OpenFDO

Authors Yuan-Hsun Lo, Ryo-Yu Pei, Hung-Lin Fu

Publication date 26 September 2013

Published in Utilitas Mathematica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0043

zbMATH Keywords

complete bipartite graphedge coloringmulticolored cycle

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we study the proper edge-colorings of the complete bipartite graph $K_{m,n}$ which forbid multicolored cycles. Mainly, we prove that (1) for any integer $kgeq2$, if $ngeq5k-6$, then any properly $n$-edge-colored $K_{k,n}$ contains a multicolored $C_{2k}$, and (2) determine the order of the properly edge-colored complete bipartite graphs which forbid multicolored $C_6$.

Review text

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, the authors study the proper edge colorings of the complete bipartite graph \(K_{m, n}\) which forbid multicolored cycles. It is proved that for any integer \(k \geq 2\), if \(n \geq 5k - 6\), then any properly \(n\)-edge colored \(K_{k, n}\) contains a multicolored \(C_{2k}\). The authors also determine the order of the properly edge-colored complete bipartite graphs which forbid multicolored \(C_6\).

Recommendations

• Multicolored parallelisms of Hamiltonian cycles
• Edge‐colored complete graphs without properly colored even cycles: A full characterization
• Edge Colorings of K(m,n) with m+n-1 Colors Which Forbid Rainbow Cycles
• Properly colored cycles of different lengths in edge-colored complete graphs
• scientific article; zbMATH DE number 5995288

Cited in

(7)

• Structure of colored complete graphs free of proper cycles
• On restricted colorings of (d, s)-edge colorable graphs
• A complete bipartite graph without properly colored cycles of length four
• Edge Colorings of K(m,n) with m+n-1 Colors Which Forbid Rainbow Cycles
• Edge-Disjoint Isomorphic Multicolored Trees and Cycles in Complete Graphs
• Edge‐colored complete graphs without properly colored even cycles: A full characterization
• Edge-colourings of \(K_{n,n}\) with no long two-coloured cycles

This page was built for publication: Edge-colorings of \(K_{m,n}\) which forbid multicolored cycles

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