错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Secant edges: a tool for Cohen et al.’s conjectures about subdivisions of oriented cycles and bispindles in Hamiltonian digraphs with large chromatic number

  • Darine Al-Mniny,
  • Salman Ghazal

摘要

Cohen et al. conjectured that, for every oriented cycle C, there is an integer f(C) such that the chromatic number of each strong digraph not containing a subdivision of C is at most f(C). In the same paper, Cohen et al. proved this conjecture for cycles with two blocks \(C(k_1,k_2)\) C ( k 1 , k 2 ) by showing that \(f(C(k_1,k_2))\) f ( C ( k 1 , k 2 ) ) is bounded from above by \(O(\{(k_1+k_2)\}^4)\) O ( { ( k 1 + k 2 ) } 4 ) . More recently, Kim et al. improved this upper bound to \(O(\{(k_1+k_2)\}^2)\) O ( { ( k 1 + k 2 ) } 2 ) . However, Addario et al. asked if the chromatic number of strong digraphs having no subdivision of \(C(k_1,k_2)\) C ( k 1 , k 2 ) can be bounded from above by \(O(k_1 + k_2)\) O ( k 1 + k 2 ) . This problem is positively answered by Kim et al. for the class of Hamiltonian digraphs. Recently, El Joubbeh confirmed Cohen et al.’s conjecture for every oriented cycle in Hamiltonian digraphs. As a generalization of two-blocks cycles, Cohen et al. conjectured that, for every positive integers \(k_1, k_2, k_3\) k 1 , k 2 , k 3 , there is an integer \(g(k_1,k_2,k_3)\) g ( k 1 , k 2 , k 3 ) such that each strong digraph not containing a subdivision of the \((2+1)\) ( 2 + 1 ) -bispindle \(B(k_1, k_2; k_3)\) B ( k 1 , k 2 ; k 3 ) has a chromatic number at most \(g(k_1, k_2, k_3)\) g ( k 1 , k 2 , k 3 ) . In the same paper, Cohen et al. proved this conjecture for the case when \(k_2=1\) k 2 = 1 , and more recently, Al-Mniny confirmed it for the case when \(k_3=1\) k 3 = 1 . In this article, we confirm Cohen et al.’s conjecture about subdivisions of \(B(k_1, k_2; k_3)\) B ( k 1 , k 2 ; k 3 ) for the class of Hamiltonian digraphs, namely \(g(k_1,k_2,k_3)\le 4.max\{k_1,k_2,k_3\}\) g ( k 1 , k 2 , k 3 ) 4 . m a x { k 1 , k 2 , k 3 } . Moreover, we provide a positive answer to Addario et al.’s problem for the class of digraphs having a Hamiltonian directed path. The proofs make use of the notion of secant edges that serves as a central tool to detect the existence of bispindles and two-blocks cycles in Hamiltonian digraphs, and that is heavily used by El Joubbeh to detect the existence of any oriented cycle in Hamiltonian digraphs.