2020/10/21 by Darine Al Mniny, Mniny, Darine Al, Salman Ghazal +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced Graph Theory Research #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2010.10787
openalex publication_date 2020/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A (2+1)-bispindle B(k1,k2;k3) is the union of two xy-dipaths of respective lengths k1 and k2, and one yx-dipath of length k3, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. conjectured that, for every positive integers k1, k2, k3, there is an integer g(k1, k2, k3) such that every strongly connected digraph not containing subdivisions of B(k1, k2; k3) has a chromatic number at most g(k1, k2, k3), and they proved it only for the case where k2=1. For Hamiltonian digraphs, we prove Cohen et al.'s conjecture, namely g(k1, k2, k3)≤ 4k, where k=max\k1, k2, k3\. A two-blocks cycle C(k1,k2) is the union of two internally disjoint xy-dipaths of length k1 and k2 respectively. Addario et al. asked if the chromatic number of strong digraphs not containing subdivisions of a two-blocks cycle C(k1,k2) can be bounded from above by O(k1+k2), which remains an open problem. Assuming that k=max\k1,k2\, the best reached upper bound, found by Kim et al., is 12k2. In this article, we conjecture that this bound can be slightly improved to 4k2 and we confirm our conjecture for some particular cases. Moreover, we provide a positive answer to Addario et al.'s question for the class of digraphs having a Hamiltonian directed path.