{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T15:17:21Z","timestamp":1776179841504,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Given a graph $G$, a vertex-colouring $\\sigma$ of $G$, and a subset $X\\subseteq V(G)$, a colour $x \\in \\sigma(X)$ is said to be odd for $X$ in $\\sigma$ if it has an odd number of occurrences in $X$. We say that $\\sigma$ is an odd colouring of $G$ if it is proper and every (open) neighbourhood has an odd colour in $\\sigma$. The odd chromatic number of a graph $G$, denoted by $\\chi_o(G)$, is the minimum $k\\in\\mathbb{N}$ such that an odd colouring $\\sigma \\colon V(G)\\to [k]$ exists. In a recent paper, Caro, Petru\u0161evski and \u0160krekovski conjectured that every connected graph of maximum degree $\\Delta\\ge 3$ has odd-chromatic number at most $\\Delta+1$. We prove that this conjecture holds asymptotically: for every connected graph $G$ with maximum degree $\\Delta$, $\\chi_o(G)\\le\\Delta+O(\\ln\\Delta)$ as $\\Delta \\to \\infty$. We also prove that $\\chi_o(G)\\le\\lfloor3\\Delta\/2\\rfloor+2$ for every $\\Delta$. If moreover the minimum degree $\\delta$ of $G$ is sufficiently large, we have $\\chi_o(G) \\le \\chi(G) + O(\\Delta \\ln \\Delta\/\\delta)$ and $\\chi_o(G) = O(\\chi(G)\\ln \\Delta)$. Finally, given an integer $h\\ge 1$, we study the generalisation of these results to $h$-odd colourings, where every vertex $v$ must have at least $\\min \\{\\deg(v),h\\}$ odd colours in its neighbourhood. Many of our results are tight up to some multiplicative constant.<\/jats:p>","DOI":"10.37236\/12110","type":"journal-article","created":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T12:33:12Z","timestamp":1732797192000},"source":"Crossref","is-referenced-by-count":4,"title":["New Bounds for Odd Colourings of Graphs"],"prefix":"10.37236","volume":"31","author":[{"given":"Tianjiao","family":"Dai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiancheng","family":"Ouyang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Pirot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2024,11,29]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i4p57\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i4p57\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T12:33:12Z","timestamp":1732797192000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v31i4p57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,29]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,10,3]]}},"URL":"https:\/\/doi.org\/10.37236\/12110","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,29]]},"article-number":"P4.57"}}