Remarks on the subdivisions of bispindles and two-blocks cycles in highly chromatic digraphs

arXiv2010.10787MaRDI QIDQ6351857FDOQ6351857

Darine Al-Mniny, Salman Ghazal

Publication date: 21 October 2020

Abstract: A $(2+1)$-bispindle $B(k_1,k_2;k_3)$ is the union of two $xy$-dipaths of respective lengths $k_1$ and $k_2$, and one $yx$-dipath of length $k_3$, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. conjectured that, for every positive integers $k_1,k_2,k_3$, there is an integer $g(k_1,k_2,k_3)$ such that every strongly connected digraph not containing subdivisions of $B(k_1,k_2;k_3)$ has a chromatic number at most $g(k_1,k_2,k_3)$, and they proved it only for the case where $k_2=1$. For Hamiltonian digraphs, we prove Cohen et al.'s conjecture, namely $g(k_1,k_2,k_3)leq4k$, where $k=max{k}_1,k_2,k_3$. A two-blocks cycle $C(k_1,k_2)$ is the union of two internally disjoint $xy$-dipaths of length $k_1$ and $k_2$ respectively. Addario et al. asked if the chromatic number of strong digraphs not containing subdivisions of a two-blocks cycle $C(k_1,k_2)$ can be bounded from above by $O(k_1+k_2)$, which remains an open problem. Assuming that $k=max{k}_1,k_2$, the best reached upper bound, found by Kim et al., is $12k^2$. In this article, we conjecture that this bound can be slightly improved to $4k^2$ 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.

This page was built for publication: Remarks on the subdivisions of bispindles and two-blocks cycles in highly chromatic digraphs

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