{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T04:01:39Z","timestamp":1750564899756,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2005,7,21]],"date-time":"2005-07-21T00:00:00Z","timestamp":1121904000000},"content-version":"unspecified","delay-in-days":20,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>The present paper deals with two graph parameters related to cover graphs and acyclic orientations of graphs.<\/jats:p>\n\t  <jats:p>The parameter <jats:inline-formula>$c(G)$<\/jats:inline-formula> of a graph <jats:inline-formula>$G$<\/jats:inline-formula>, introduced by B. Bollob\u00e1s, G. Brightwell and J. Ne\u0161et\u0159il [<jats:italic>Order<\/jats:italic><jats:bold>3<\/jats:bold> 245\u2013255], is defined as the minimum number of edges one needs to delete from <jats:inline-formula>$G$<\/jats:inline-formula> in order to obtain a cover graph. Extending their results, we prove that, for <jats:inline-formula>$\\delta &gt;0$<\/jats:inline-formula>, <jats:inline-formula>$(1-\\delta) \\frac{1}{l} \\frac{n^2p}{2} \\leq c({\\mathcal G}_{n,p}) \\leq (1+\\delta) \\frac{1}{l} \\frac{n^2p}{2}$<\/jats:inline-formula> asymptotically almost surely as long as <jats:inline-formula>$C n^{-1 + \\frac{1}{l}} \\leq p(n) \\leq c n^{-1 + \\frac{1}{ l-1} }$<\/jats:inline-formula> for some positive constants <jats:inline-formula>$c$<\/jats:inline-formula> and <jats:inline-formula>$C$<\/jats:inline-formula>. Here, as usual, <jats:inline-formula>${\\mathcal G}_{n,p}$<\/jats:inline-formula> is the random graph.<\/jats:p>\n\t  <jats:p>Given an acyclic orientation of a graph <jats:inline-formula>$G$<\/jats:inline-formula>, an arc is called dependent if its reversal creates an oriented cycle. Let <jats:inline-formula>$d_{\\min}(G)$<\/jats:inline-formula> be the minimum number of dependent arcs in any acyclic orientation of <jats:inline-formula>$G$<\/jats:inline-formula>. We determine the supremum, denoted by <jats:inline-formula>$r_{\\chi,g}$<\/jats:inline-formula>, of <jats:inline-formula>$d_{\\min}(G)\/e(G)$<\/jats:inline-formula> in the class of graphs <jats:inline-formula>$G$<\/jats:inline-formula> with chromatic number <jats:inline-formula>$\\chi$<\/jats:inline-formula> and girth <jats:inline-formula>$g$<\/jats:inline-formula>. Namely, we show that <jats:inline-formula>$r_{\\chi,g} = {(\\scriptsize\\begin{array}{@{}c@{}}{\\chi}-g+2\\\\ 2\\end{array})} \/ {(\\scriptsize\\begin{array}{@{}c@{}}{\\chi}\\\\ 2\\end{array})}$<\/jats:inline-formula>. This extends results of D. C. Fisher, K. Fraughnaugh, L. Langley and D. B. West [<jats:italic>J. Combin. Theory Ser. B<\/jats:italic><jats:bold>71<\/jats:bold> 73\u201378].<\/jats:p>","DOI":"10.1017\/s0963548305006760","type":"journal-article","created":{"date-parts":[[2005,7,21]],"date-time":"2005-07-21T11:25:21Z","timestamp":1121945121000},"page":"585-617","source":"Crossref","is-referenced-by-count":5,"title":["On Cover Graphs and Dependent Arcs in Acyclic Orientations"],"prefix":"10.1017","volume":"14","author":[{"given":"V.","family":"R\u00d6DL","sequence":"first","affiliation":[]},{"given":"L.","family":"THOMA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2005,7,21]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548305006760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T03:56:16Z","timestamp":1750478176000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548305006760\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["S0963548305006760"],"URL":"https:\/\/doi.org\/10.1017\/s0963548305006760","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2005,7]]}}}