Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–7 of 7 results for author: <span class="mathjax">de Verclos, R d J</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=de+Verclos%2C+R+d+J">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="de Verclos, R d J"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=de+Verclos%2C+R+d+J&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="de Verclos, R d J"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2007.07874">arXiv:2007.07874</a> <span> [<a href="https://arxiv.org/pdf/2007.07874">pdf</a>, <a href="https://arxiv.org/format/2007.07874">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.19086/aic.2022.7">10.19086/aic.2022.7 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> An improved procedure for colouring graphs of bounded local density </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hurley%2C+E">Eoin Hurley</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2007.07874v3-abstract-short" style="display: inline;"> We develop an improved bound for the chromatic number of graphs of maximum degree $螖$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-蟽)\binom螖{2}$ for some fixed $0<蟽<1$. The leading term in the reduction of colours achieved through this bound is best possible as $蟽\to0$. As two consequences, we advance the state of the art in two longstanding and well-stud… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.07874v3-abstract-full').style.display = 'inline'; document.getElementById('2007.07874v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2007.07874v3-abstract-full" style="display: none;"> We develop an improved bound for the chromatic number of graphs of maximum degree $螖$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-蟽)\binom螖{2}$ for some fixed $0<蟽<1$. The leading term in the reduction of colours achieved through this bound is best possible as $蟽\to0$. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erd艖s-Ne拧et艡il conjecture and Reed's conjecture. We prove that the strong chromatic index is at most $1.772螖^2$ for any graph $G$ with sufficiently large maximum degree $螖$. We prove that the chromatic number is at most $\lceil 0.881(螖+1)+0.119蠅\rceil$ for any graph $G$ with clique number $蠅$ and sufficiently large maximum degree $螖$. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-蟽)螖$, and establish what may be considered first progress towards a conjecture of Vu. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.07874v3-abstract-full').style.display = 'none'; document.getElementById('2007.07874v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 15 July, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">33 pages; in v2 corrected the Reed's conjecture bound, added appendix on Talagrand's, added adaptation towards Vu's conjecture; v3 final published version</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15 (primary); 05C35; 05D40 (secondary) </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Advances in Combinatorics, 2022:7, 33pp </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1912.13328">arXiv:1912.13328</a> <span> [<a href="https://arxiv.org/pdf/1912.13328">pdf</a>, <a href="https://arxiv.org/ps/1912.13328">ps</a>, <a href="https://arxiv.org/format/1912.13328">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Structure and colour in triangle-free graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Aravind%2C+N+R">N. R. Aravind</a>, <a href="/search/cs?searchtype=author&query=Cambie%2C+S">Stijn Cambie</a>, <a href="/search/cs?searchtype=author&query=van+Batenburg%2C+W+C">Wouter Cames van Batenburg</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Patel%2C+V">Viresh Patel</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1912.13328v2-abstract-short" style="display: inline;"> Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $蠂$ contains a rainbow independent set of size $\lceil\frac12蠂\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13328v2-abstract-full').style.display = 'inline'; document.getElementById('1912.13328v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1912.13328v2-abstract-full" style="display: none;"> Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $蠂$ contains a rainbow independent set of size $\lceil\frac12蠂\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $蠂$ contains an induced cycle of length $惟(蠂\log蠂)$ as $蠂\to\infty$. Even if one only demands an induced path of length $惟(蠂\log蠂)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13328v2-abstract-full').style.display = 'none'; document.getElementById('1912.13328v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 March, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 31 December, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages; in v2 one section was removed due to a subtle error</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1905.06031">arXiv:1905.06031</a> <span> [<a href="https://arxiv.org/pdf/1905.06031">pdf</a>, <a href="https://arxiv.org/ps/1905.06031">ps</a>, <a href="https://arxiv.org/format/1905.06031">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Strong chromatic index and Hadwiger number </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=van+Batenburg%2C+W+C">Wouter Cames van Batenburg</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pirot%2C+F">Fran莽ois Pirot</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1905.06031v2-abstract-short" style="display: inline;"> We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each $k\ge 4$ that any $K_k$-minor-free multigraph of maximum degree $螖$ has strong chromatic index at most $\frac32(k-2)螖$. We present a construction certifying that if true the conjecture is asymptotically sharp as $螖\to\infty$. In support of… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.06031v2-abstract-full').style.display = 'inline'; document.getElementById('1905.06031v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1905.06031v2-abstract-full" style="display: none;"> We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each $k\ge 4$ that any $K_k$-minor-free multigraph of maximum degree $螖$ has strong chromatic index at most $\frac32(k-2)螖$. We present a construction certifying that if true the conjecture is asymptotically sharp as $螖\to\infty$. In support of the conjecture, we show it in the case $k=4$ and prove the statement for strong clique number in place of strong chromatic index. By contrast, we make a basic observation that for $K_k$-minor-free simple graphs, the problem of strong edge-colouring is "between" Hadwiger's Conjecture and its fractional relaxation. For $k\geq5$, we also show that $K_k$-minor-free multigraphs of edge-diameter at most $2$ have strong clique number at most $(k-\frac{1}{2})螖$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.06031v2-abstract-full').style.display = 'none'; document.getElementById('1905.06031v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 August, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 15 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">23 pages, 4 figures; v2 includes minor corrections, to appear in Journal of Graph Theory</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15 (primary); 05C10; 05C72; 05C83 (secondary) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1812.11152">arXiv:1812.11152</a> <span> [<a href="https://arxiv.org/pdf/1812.11152">pdf</a>, <a href="https://arxiv.org/ps/1812.11152">ps</a>, <a href="https://arxiv.org/format/1812.11152">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> </div> <p class="title is-5 mathjax"> Occupancy fraction, fractional colouring, and triangle fraction </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Davies%2C+E">Ewan Davies</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pirot%2C+F">Fran莽ois Pirot</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1812.11152v2-abstract-short" style="display: inline;"> Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le 螖^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $螖$ in which the neighbourhood of every vertex in $G$ spans at most $螖^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/螖)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at mo… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.11152v2-abstract-full').style.display = 'inline'; document.getElementById('1812.11152v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1812.11152v2-abstract-full" style="display: none;"> Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le 螖^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $螖$ in which the neighbourhood of every vertex in $G$ spans at most $螖^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/螖)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)螖/\log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as stronger versions of results of Ajtai, Koml贸s and Szemer茅di (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.11152v2-abstract-full').style.display = 'none'; document.getElementById('1812.11152v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 December, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 December, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">13 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C35; 05D10 (Primary); 05C15 (Secondary) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1812.01534">arXiv:1812.01534</a> <span> [<a href="https://arxiv.org/pdf/1812.01534">pdf</a>, <a href="https://arxiv.org/ps/1812.01534">ps</a>, <a href="https://arxiv.org/format/1812.01534">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1002/rsa.20945">10.1002/rsa.20945 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Colouring triangle-free graphs with local list sizes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Davies%2C+E">Ewan Davies</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pirot%2C+F">Fran莽ois Pirot</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1812.01534v2-abstract-short" style="display: inline;"> We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractiona… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.01534v2-abstract-full').style.display = 'inline'; document.getElementById('1812.01534v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1812.01534v2-abstract-full" style="display: none;"> We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1812.01534v2-abstract-full').style.display = 'none'; document.getElementById('1812.01534v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 16 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 December, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">16 pages; v2 includes minor corrections after review; to appear in Random Structures & Algorithms</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C35; 05C15; 05D10 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1808.02512">arXiv:1808.02512</a> <span> [<a href="https://arxiv.org/pdf/1808.02512">pdf</a>, <a href="https://arxiv.org/ps/1808.02512">ps</a>, <a href="https://arxiv.org/format/1808.02512">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Bipartite induced density in triangle-free graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=van+Batenburg%2C+W+C">Wouter Cames van Batenburg</a>, <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pirot%2C+F">Fran莽ois Pirot</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1808.02512v3-abstract-short" style="display: inline;"> We prove that any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$. Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$. This is sharp up to… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1808.02512v3-abstract-full').style.display = 'inline'; document.getElementById('1808.02512v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1808.02512v3-abstract-full" style="display: none;"> We prove that any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$. Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$. This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most $O(\min\{\sqrt{n},(n\log n)/d\})$ as $n\to\infty$. Relatedly, we also make two conjectures. First, any triangle-free graph on $n$ vertices has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\log n}$ as $n\to\infty$. Second, any triangle-free graph on $n$ vertices has list chromatic number at most $O(\sqrt{n/\log n})$ as $n\to\infty$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1808.02512v3-abstract-full').style.display = 'none'; document.getElementById('1808.02512v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 August, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages; in v2 added note of concurrent work and one reference; in v3 added more notes of ensuing work and a result towards one of the conjectures (for list colouring)</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C35; 05C15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1609.08645">arXiv:1609.08645</a> <span> [<a href="https://arxiv.org/pdf/1609.08645">pdf</a>, <a href="https://arxiv.org/ps/1609.08645">ps</a>, <a href="https://arxiv.org/format/1609.08645">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Colouring squares of claw-free graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=de+Verclos%2C+R+d+J">R茅mi de Joannis de Verclos</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pastor%2C+L">Lucas Pastor</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1609.08645v3-abstract-short" style="display: inline;"> Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $蠂(G^2) \le (2-\varepsilon) 蠅(G)^2$, where $蠅(G)$ is the clique number of $G$? Erd艖s and Ne拧et艡il asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.08645v3-abstract-full').style.display = 'inline'; document.getElementById('1609.08645v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1609.08645v3-abstract-full" style="display: none;"> Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $蠂(G^2) \le (2-\varepsilon) 蠅(G)^2$, where $蠅(G)$ is the clique number of $G$? Erd艖s and Ne拧et艡il asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erd艖s and Ne拧et艡il. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.08645v3-abstract-full').style.display = 'none'; document.getElementById('1609.08645v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 July, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 September, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">19 pages; v2 corrects for a subtlety in the original derivation of Thm 1; v3 accepted to Canadian Journal of Mathematics</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15 (primary); 05C35; 05C70 (secondary) </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository