{
  "id": "2308.13640",
  "version": "v1",
  "published": "2023-08-25T19:20:18.000Z",
  "updated": "2023-08-25T19:20:18.000Z",
  "title": "About subdivisions of four blocks cycles $C(k_1,1,k_3,1)$ in digraphs with large chromatic number",
  "authors": [
    "Darine Al-Mniny",
    "Soukaina Zayat"
  ],
  "comment": "23 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A cycle with four blocks $C(k_{1}, k_{2},k_{3},k_{4})$ is an oriented cycle formed of four blocks of lengths $k_{1}, k_{2}, k_{3}$ and $k_{4}$ respectively. Recently, Cohen et al. conjectured that for every positive integers $k_{1}, k_{2}, k_{3}, k_{4}$, there is an integer $g(k_{1},k_{2},k_{3},k_{4})$ such that every strongly connected digraph $D$ containing no subdivisions of $C(k_{1},k_{2},k_{3},k_{4})$ has a chromatic number at most $g(k_{1},k_{2},k_{3},k_{4})$. 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(k_1,1,1,1)$. In this paper, we affirm Cohen et al.'s conjecture for the case where $k_2=k_4=1$, namely $g(k_1,1,k_3,1) =O({(k_1+k_3)}^2)$. Moreover, we show that if in addition $D$ is Hamiltonian, then the chromatic number of $D$ is at most $6k$, with $k=\\textrm{max}\\{k_1,k_3\\}.$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-25T19:20:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large chromatic number",
      "blocks cycles",
      "subdivisions",
      "conjecture",
      "affirm cohen"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}