{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:44Z","timestamp":1753893824777,"version":"3.41.2"},"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>Tuza [1992] proved that a graph with no cycles of length congruent to $1$ modulo $k$ is $k$-colorable.\u00a0 We prove that if a graph $G$ has an edge $e$ such that $G-e$ is $k$-colorable and $G$ is not, then for $2\\le r\\le k$, the edge $e$ lies in at least $\\prod_{i=1}^{r-1} (k-i)$ cycles of length $1\\mod r$ in $G$, and $G-e$ contains at least $\\frac12{\\prod_{i=1}^{r-1} (k-i)}$ cycles of length $0 \\mod r$.\r\nA $(k,d)$-coloring of $G$ is a homomorphism from $G$ to the graph $K_{k:d}$ with vertex set ${\\mathbb Z}_{k}$ defined by making $i$ and $j$ adjacent if $d\\le j-i \\le k-d$.\u00a0 When $k$ and $d$ are relatively prime, define $s$ by $sd\\equiv 1\\mod k$.\u00a0 A result of Zhu [2002] implies that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $i\\in \\{1,\\ldots,2d-1\\}$.\u00a0 In fact, only $d$ classes need be excluded: we prove that if $G-e$ is $(k,d)$-colorable and $G$ is not, then $e$ lies in at least one cycle with length congruent to $is\\mod k$ for some $i$ in $\\{1,\\ldots,d\\}$.\u00a0 Furthermore, if this does not occur with $i\\in\\{1,\\ldots,d-1\\}$, then $e$ lies in at least two cycles with length $1\\mod k$ and $G-e$ contains a cycle of length $0 \\mod k$.<\/jats:p>","DOI":"10.37236\/10177","type":"journal-article","created":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T02:05:24Z","timestamp":1638497124000},"source":"Crossref","is-referenced-by-count":1,"title":["Cycles in Color-Critical Graphs"],"prefix":"10.37236","volume":"28","author":[{"given":"Benjamin R.","family":"Moore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas B.","family":"West","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2021,12,3]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i4p35\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i4p35\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T02:05:25Z","timestamp":1638497125000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i4p35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,3]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,10,8]]}},"URL":"https:\/\/doi.org\/10.37236\/10177","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2021,12,3]]},"article-number":"P4.35"}}