{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:50:57Z","timestamp":1754110257343,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>We prove that if $G$ is the line graph of a multigraph, then the chromatic number $\\chi(G)$ of $G$ is at most $\\max\\left\\{\\omega(G), \\frac{7\\Delta(G) + 10}{8}\\right\\}$ where $\\omega(G)$ and $\\Delta(G)$ are the  clique number and the maximum degree of $G$, respectively.  Thus Brooks' Theorem holds for line graphs of multigraphs in much stronger form.  Using similar methods we then prove that if $G$ is the line graph of a multigraph with $\\chi(G) \\geq \\Delta(G) \\geq 9$, then $G$ contains a clique on $\\Delta(G)$ vertices. Thus the Borodin-Kostochka Conjecture holds for line graphs of multigraphs.<\/jats:p>","DOI":"10.37236\/632","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T03:44:04Z","timestamp":1578714244000},"source":"Crossref","is-referenced-by-count":3,"title":["A Strengthening of Brooks' Theorem for Line Graphs"],"prefix":"10.37236","volume":"18","author":[{"given":"Landon","family":"Rabern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2011,7,15]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p145\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p145\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T23:08:08Z","timestamp":1579302488000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v18i1p145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,15]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,1,5]]}},"URL":"https:\/\/doi.org\/10.37236\/632","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2011,7,15]]},"article-number":"P145"}}