2023/08/25 by Darine Al-Mniny, Al-Mniny, Darine, Soukaina Zayat +1 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2308.13640
openalex publication_date 2023/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A cycle with four blocks C(k1, k2,k3,k4) is an oriented cycle formed of four blocks of lengths k1, k2, k3 and k4 respectively. Recently, Cohen et al. conjectured that for every positive integers k1, k2, k3, k4, there is an integer g(k1,k2,k3,k4) such that every strongly connected digraph D containing no subdivisions of C(k1,k2,k3,k4) has a chromatic number at most g(k1,k2,k3,k4). This conjecture is confirmed by Cohen et al. for the case of C(1,1,1,1) and by Al-Mniny for the case of C(k1,1,1,1). In this paper, we affirm Cohen et al.'s conjecture for the case where k2=k4=1, namely g(k1,1,k3,1) =O((k1+k3)2). Moreover, we show that if in addition D is Hamiltonian, then the chromatic number of D is at most 6k, with k=\textrmmax\k1,k3\.