Properly Colored Hamiltonian Paths in 2-Edge-Colored Complete Bipartite Graphs

Abstract

Properly colored subgraphs, in which no two adjacent edges share the same color, play a central role in the study of edge-colored graphs. A classical result establishes that a 2-edge-colored complete graph contains a properly colored Hamiltonian path if and only if it admits a properly colored 1-path-cycle factor. This foundational insight inspired the BJG Conjecture, later proven as the BJG Theorem, which asserts that the same characterization holds for complete graphs under any number of colors. Extending this line of inquiry, the Bipartite Extension of the BJG Theorem was proposed, conjecturing that properly colored 1-path-cycle factors similarly characterize Hamiltonian paths in edge-colored balanced complete bipartite graphs. In this work, we confirm this conjecture for the case of 2-edge-colored balanced complete bipartite graphs, establishing a bipartite analogue of the original theorem. Consequently, we show that deciding whether such a graph admits a properly colored Hamiltonian path can be performed in polynomial time and provide a constructive, polynomial-time algorithm for finding such paths. These results not only advance the structural understanding of color-constrained Hamiltonicity in bipartite graphs but also lay a foundation for future research on multi-color generalizations and practical algorithmic applications.