Properly Colored Hamiltonian Paths in 2-Edge-Colored Complete Bipartite Graphs
Hacettepe Journal of Mathematics and Statistics · 17.08.2026 · (Advanced Online Publication)
DOI: 10.15672/hujms.1797958 ↗Kurz gefasst
Fachartikel in der Zeitschrift Hacettepe Journal of Mathematics and Statistics, online erschienen am 17.08.2026. Verfasst von Yasemin Büyükçolak. Die Arbeit nennt 1 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Büyükçolak, Y. (2026). Properly Colored Hamiltonian Paths in 2-Edge-Colored Complete Bipartite Graphs. Hacettepe Journal of Mathematics and Statistics. https://doi.org/10.15672/hujms.1797958
Vancouver
Büyükçolak Y. Properly Colored Hamiltonian Paths in 2-Edge-Colored Complete Bipartite Graphs. Hacettepe Journal of Mathematics and Statistics. 2026. doi:10.15672/hujms.1797958
BibTeX
@article{Bykolak2026,
author = {Büyükçolak, Yasemin},
title = {Properly Colored Hamiltonian Paths in 2-Edge-Colored Complete Bipartite Graphs},
journal = {Hacettepe Journal of Mathematics and Statistics},
year = {2026},
number = {Advanced Online Publication},
doi = {10.15672/hujms.1797958}
}
EUVIMED