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–19 of 19 results for author: <span class="mathjax">Kang, R 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=Kang%2C+R+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="Kang, R 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=Kang%2C+R+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="Kang, R 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/2411.07985">arXiv:2411.07985</a> <span> [<a href="https://arxiv.org/pdf/2411.07985">pdf</a>, <a href="https://arxiv.org/ps/2411.07985">ps</a>, <a href="https://arxiv.org/format/2411.07985">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"> Largest component in Boolean sublattices </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Galliano%2C+J">Julian Galliano</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="2411.07985v1-abstract-short" style="display: inline;"> For a subfamily ${F}\subseteq 2^{[n]}$ of the Boolean lattice, consider the graph $G_{F}$ on ${F}$ based on the pairwise inclusion relations among its members. Given a positive integer $t$, how large can ${F}$ be before $G_{F}$ must contain some component of order greater than $t$? For $t=1$, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Bool… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.07985v1-abstract-full').style.display = 'inline'; document.getElementById('2411.07985v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.07985v1-abstract-full" style="display: none;"> For a subfamily ${F}\subseteq 2^{[n]}$ of the Boolean lattice, consider the graph $G_{F}$ on ${F}$ based on the pairwise inclusion relations among its members. Given a positive integer $t$, how large can ${F}$ be before $G_{F}$ must contain some component of order greater than $t$? For $t=1$, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For $t=2^n$, this question is trivial. We are interested in what happens between these two extremes. For $t=2^{g}$ with $g=g(n)$ being any integer function that satisfies $g(n)=o(n/\log n)$ as $n\to\infty$, we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer. This constitutes a nontrivial generalisation of Sperner's theorem. We do so by a reduction to a Tur谩n-type problem for rainbow cycles in properly edge-coloured graphs. Among other results, we also give a sharp answer to the question, how large can ${F}$ be before $G_{F}$ must be connected? <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.07985v1-abstract-full').style.display = 'none'; document.getElementById('2411.07985v1-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </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, 2 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05D05; 06A07; 05C35 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.04367">arXiv:2407.04367</a> <span> [<a href="https://arxiv.org/pdf/2407.04367">pdf</a>, <a href="https://arxiv.org/ps/2407.04367">ps</a>, <a href="https://arxiv.org/format/2407.04367">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="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Reconfiguration of Independent Transversals </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Buys%2C+P">Pjotr Buys</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Ozeki%2C+K">Kenta Ozeki</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="2407.04367v1-abstract-short" style="display: inline;"> Given integers $螖\ge 2$ and $t\ge 2螖$, suppose there is a graph of maximum degree $螖$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2螖+1$, then every independent transversal can be transformed withi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.04367v1-abstract-full').style.display = 'inline'; document.getElementById('2407.04367v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.04367v1-abstract-full" style="display: none;"> Given integers $螖\ge 2$ and $t\ge 2螖$, suppose there is a graph of maximum degree $螖$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2螖+1$, then every independent transversal can be transformed within the space of independent transversals to any other through a sequence of one-vertex modifications, showing connectivity of the so-called reconfigurability graph of independent transversals. This is sharp in that for $t=2螖$ (and $螖\ge 2$) the connectivity conclusion can fail. In this case we show furthermore that in an essential sense it can only fail for the disjoint union of copies of the complete bipartite graph $K_{螖,螖}$. This constitutes a qualitative strengthening of Haxell's theorem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.04367v1-abstract-full').style.display = 'none'; document.getElementById('2407.04367v1-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> 5 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C35; 05C69; 05C15; 68R05; 68R10 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.06072">arXiv:2309.06072</a> <span> [<a href="https://arxiv.org/pdf/2309.06072">pdf</a>, <a href="https://arxiv.org/ps/2309.06072">ps</a>, <a href="https://arxiv.org/format/2309.06072">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"> The $蠂$-binding function of $d$-directional segment graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Duraj%2C+L">Lech Duraj</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=La%2C+H">Hoang La</a>, <a href="/search/cs?searchtype=author&query=Narboni%2C+J">Jonathan Narboni</a>, <a href="/search/cs?searchtype=author&query=Pokr%C3%BDvka%2C+F">Filip Pokr媒vka</a>, <a href="/search/cs?searchtype=author&query=Rambaud%2C+C">Cl茅ment Rambaud</a>, <a href="/search/cs?searchtype=author&query=Reinald%2C+A">Amadeus Reinald</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="2309.06072v1-abstract-short" style="display: inline;"> Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $蠅$ that the chromatic number $蠂(G)$ of $G$ is at most $d蠅$. We show for every even value of $蠅$ ho… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.06072v1-abstract-full').style.display = 'inline'; document.getElementById('2309.06072v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.06072v1-abstract-full" style="display: none;"> Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $蠅$ that the chromatic number $蠂(G)$ of $G$ is at most $d蠅$. We show for every even value of $蠅$ how to construct a graph in $d$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvo艡谩k and Noorizadeh. Furthermore, we show that the $蠂$-binding function of $d$-DIR is $蠅\mapsto d蠅$ for $蠅$ even and $蠅\mapsto d(蠅-1)+1$ for $蠅$ odd. This refutes said conjecture of Bhattacharya, Dvo艡谩k and Noorizadeh. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.06072v1-abstract-full').style.display = 'none'; document.getElementById('2309.06072v1-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 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </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">11 pages, 3 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15; 05C62; 05C17 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2308.14778">arXiv:2308.14778</a> <span> [<a href="https://arxiv.org/pdf/2308.14778">pdf</a>, <a href="https://arxiv.org/ps/2308.14778">ps</a>, <a href="https://arxiv.org/format/2308.14778">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"> A precise condition for independent transversals in bipartite covers </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cambie%2C+S">Stijn Cambie</a>, <a href="/search/cs?searchtype=author&query=Haxell%2C+P">Penny Haxell</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Wdowinski%2C+R">Ronen Wdowinski</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="2308.14778v2-abstract-short" style="display: inline;"> Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp.~$V_B$) has degree at most $D_A$ (resp.~$D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp.~$V_B$) have size at least $k_A$ (resp.~$k_B$). We prove that the condition $D_A/k_B+D_B/k_A\le 1$ is sufficient for the existence of an independe… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.14778v2-abstract-full').style.display = 'inline'; document.getElementById('2308.14778v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2308.14778v2-abstract-full" style="display: none;"> Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp.~$V_B$) has degree at most $D_A$ (resp.~$D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp.~$V_B$) have size at least $k_A$ (resp.~$k_B$). We prove that the condition $D_A/k_B+D_B/k_A\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szab贸 and Tardos. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2308.14778v2-abstract-full').style.display = 'none'; document.getElementById('2308.14778v2-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 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2023. </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">10 pages, 2 figures; v2 is AAM accepted to SIDMA after incorporating minor corrections</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C69; 05D15; 05C15; 05C35 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2110.05230">arXiv:2110.05230</a> <span> [<a href="https://arxiv.org/pdf/2110.05230">pdf</a>, <a href="https://arxiv.org/ps/2110.05230">ps</a>, <a href="https://arxiv.org/format/2110.05230">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.21181">10.1002/rsa.21181 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Packing list-colourings </p> <p class="authors"> <span class="search-hit">Authors:</span> <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=Davies%2C+E">Ewan Davies</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="2110.05230v2-abstract-short" style="display: inline;"> List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a $k$-list-assignment $L$ of a graph $G$, which is the assignment of a list… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.05230v2-abstract-full').style.display = 'inline'; document.getElementById('2110.05230v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2110.05230v2-abstract-full" style="display: none;"> List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a $k$-list-assignment $L$ of a graph $G$, which is the assignment of a list $L(v)$ of $k$ colours to each vertex $v\in V(G)$, we study the existence of $k$ pairwise-disjoint proper colourings of $G$ using colours from these lists. We may refer to this as a \emph{list-packing}. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest $k$ for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of $G$. (The reader might already find it interesting that such a minimal $k$ is well defined.) We also pursue a more focused study of the case when $G$ is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal $k$ above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalisations of the problem above in the same spirit. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.05230v2-abstract-full').style.display = 'none'; document.getElementById('2110.05230v2-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> 3 March, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2021. </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">32 pages, 2 tables; v2 accepted to Random Structures & Algorithms</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15; 05C35; 05C69; 05C70 </p> </li> <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/2004.07151">arXiv:2004.07151</a> <span> [<a href="https://arxiv.org/pdf/2004.07151">pdf</a>, <a href="https://arxiv.org/format/2004.07151">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> An algorithmic framework for colouring locally sparse graphs </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=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Pirot%2C+F">Fran莽ois Pirot</a>, <a href="/search/cs?searchtype=author&query=Sereni%2C+J">Jean-S茅bastien Sereni</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="2004.07151v1-abstract-short" style="display: inline;"> We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $螖$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.07151v1-abstract-full').style.display = 'inline'; document.getElementById('2004.07151v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2004.07151v1-abstract-full" style="display: none;"> We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $螖$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le 螖^\frac{2\varepsilon}{1+2\varepsilon}/(\log螖)^2$, with $\lfloor(1+\varepsilon)螖/\log(螖/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.07151v1-abstract-full').style.display = 'none'; document.getElementById('2004.07151v1-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 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 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">23 pages</span> </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/1805.02156">arXiv:1805.02156</a> <span> [<a href="https://arxiv.org/pdf/1805.02156">pdf</a>, <a href="https://arxiv.org/ps/1805.02156">ps</a>, <a href="https://arxiv.org/format/1805.02156">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"> Tree-like distance colouring for planar graphs of sufficient girth </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=van+Loon%2C+W">Willem van Loon</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="1805.02156v2-abstract-short" style="display: inline;"> Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $蟺'_t(d)$ and $蟿'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, r… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1805.02156v2-abstract-full').style.display = 'inline'; document.getElementById('1805.02156v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1805.02156v2-abstract-full" style="display: none;"> Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $蟺'_t(d)$ and $蟿'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$. We have that $蟺'_t(d)$ is at most and at least a non-trivial constant multiple larger than $蟿'_t(d)$. (We conjecture $\limsup_{d\to\infty}蟺'_2(d)/蟿'_2(d) =9/4$ in particular.) We prove for odd $t$ the existence of a quantity $g$ depending only on $t$ such that the distance-$t$ chromatic index of any planar multigraph of maximum degree $d$ and girth at least $g$ is at most $蟿'_t(d)$ if $d$ is sufficiently large. Such a quantity does not exist for even $t$. We also show a related, similar phenomenon for distance vertex-colouring. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1805.02156v2-abstract-full').style.display = 'none'; document.getElementById('1805.02156v2-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> 6 February, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 6 May, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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, 1 figure; v2 to appear in Electronic Journal of Combinatorics</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15; 05C35 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1803.10962">arXiv:1803.10962</a> <span> [<a href="https://arxiv.org/pdf/1803.10962">pdf</a>, <a href="https://arxiv.org/ps/1803.10962">ps</a>, <a href="https://arxiv.org/format/1803.10962">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"> Single-conflict colouring </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dvo%C5%99%C3%A1k%2C+Z">Zden臎k Dvo艡谩k</a>, <a href="/search/cs?searchtype=author&query=Esperet%2C+L">Louis Esperet</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Ozeki%2C+K">Kenta Ozeki</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="1803.10962v2-abstract-short" style="display: inline;"> Given a multigraph, suppose that each vertex is given a local assignment of $k$ colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least $k$ for which this is always possible given any set of local assignments we call the {\em single-conflict chromatic number} of the graph. This pa… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1803.10962v2-abstract-full').style.display = 'inline'; document.getElementById('1803.10962v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1803.10962v2-abstract-full" style="display: none;"> Given a multigraph, suppose that each vertex is given a local assignment of $k$ colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least $k$ for which this is always possible given any set of local assignments we call the {\em single-conflict chromatic number} of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus $g$ is $O(g^{1/4}\log g)$ as $g\to\infty$. This is sharp up to the logarithmic factor. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1803.10962v2-abstract-full').style.display = 'none'; document.getElementById('1803.10962v2-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> 9 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 March, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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">15 pages; in v2, changed the main terminology, added one example, adjusted Conjecture 3; 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 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1802.03727">arXiv:1802.03727</a> <span> [<a href="https://arxiv.org/pdf/1802.03727">pdf</a>, <a href="https://arxiv.org/ps/1802.03727">ps</a>, <a href="https://arxiv.org/format/1802.03727">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.1017/S0963548319000026">10.1017/S0963548319000026 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Separation choosability and dense bipartite induced subgraphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Esperet%2C+L">Louis Esperet</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Thomass%C3%A9%2C+S">St茅phan Thomass茅</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="1802.03727v2-abstract-short" style="display: inline;"> We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This st… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1802.03727v2-abstract-full').style.display = 'inline'; document.getElementById('1802.03727v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1802.03727v2-abstract-full" style="display: none;"> We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree $d$ contain a bipartite induced subgraph of minimum degree $惟(\log d)$ as $d\to\infty$? <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1802.03727v2-abstract-full').style.display = 'none'; document.getElementById('1802.03727v2-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> 4 December, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 February, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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">18 pages; v2 accepted to Combinatorics, Probability & Computing</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C15; 05C35 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Combinator. Probab. Comp. 28 (2019) 720-732 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1609.08646">arXiv:1609.08646</a> <span> [<a href="https://arxiv.org/pdf/1609.08646">pdf</a>, <a href="https://arxiv.org/ps/1609.08646">ps</a>, <a href="https://arxiv.org/format/1609.08646">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.4153/CMB-2018-024-5">10.4153/CMB-2018-024-5 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Squared chromatic number without claws or large cliques </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=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="1609.08646v3-abstract-short" style="display: inline;"> Let $G$ be a claw-free graph on $n$ vertices with clique number $蠅$, and consider the chromatic number $蠂(G^2)$ of the square $G^2$ of $G$. Writing $蠂'_s(d)$ for the supremum of $蠂(L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $蠂(G^2)\le 蠂'_s(蠅)$ for $蠅\in \{3,4\}$. For $蠅=3$, this implies the sharp bound $蠂(G^2) \leq 10$. For $蠅=4$, this implies… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.08646v3-abstract-full').style.display = 'inline'; document.getElementById('1609.08646v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1609.08646v3-abstract-full" style="display: none;"> Let $G$ be a claw-free graph on $n$ vertices with clique number $蠅$, and consider the chromatic number $蠂(G^2)$ of the square $G^2$ of $G$. Writing $蠂'_s(d)$ for the supremum of $蠂(L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $蠂(G^2)\le 蠂'_s(蠅)$ for $蠅\in \{3,4\}$. For $蠅=3$, this implies the sharp bound $蠂(G^2) \leq 10$. For $蠅=4$, this implies $蠂(G^2)\leq 22$, which is within $2$ of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erd艖s and Ne拧et艡il. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.08646v3-abstract-full').style.display = 'none'; document.getElementById('1609.08646v3-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> 17 May, 2018; <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">13 pages; v2 corrects for a subtlety in the original derivation of Thm 1.2; v3 accepted to Canadian Mathematical Bulletin</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 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Can. Math. Bull. 62 (2019) 23-35 </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> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1303.4336">arXiv:1303.4336</a> <span> [<a href="https://arxiv.org/pdf/1303.4336">pdf</a>, <a href="https://arxiv.org/ps/1303.4336">ps</a>, <a href="https://arxiv.org/format/1303.4336">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"> Supersaturation in the Boolean lattice </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dove%2C+A+P">Andrew P. Dove</a>, <a href="/search/cs?searchtype=author&query=Griggs%2C+J+R">Jerrold R. Griggs</a>, <a href="/search/cs?searchtype=author&query=Kang%2C+R+J">Ross J. Kang</a>, <a href="/search/cs?searchtype=author&query=Sereni%2C+J">Jean-S茅bastien Sereni</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="1303.4336v1-abstract-short" style="display: inline;"> We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains. Our result implies that a largest family whose size is x more than the size of a largest k-chain free family and that contains the minimum number of k-chains is the family formed by taking the middle (k-1) rows of the Boolean lattice and x elements from the k-th middle r… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1303.4336v1-abstract-full').style.display = 'inline'; document.getElementById('1303.4336v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1303.4336v1-abstract-full" style="display: none;"> We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains. Our result implies that a largest family whose size is x more than the size of a largest k-chain free family and that contains the minimum number of k-chains is the family formed by taking the middle (k-1) rows of the Boolean lattice and x elements from the k-th middle row. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1303.4336v1-abstract-full').style.display = 'none'; document.getElementById('1303.4336v1-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 March, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Integers 14A (2014): #A4 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1102.3635">arXiv:1102.3635</a> <span> [<a href="https://arxiv.org/pdf/1102.3635">pdf</a>, <a href="https://arxiv.org/ps/1102.3635">ps</a>, <a href="https://arxiv.org/format/1102.3635">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="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bordewich%2C+M">Magnus Bordewich</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="1102.3635v1-abstract-short" style="display: inline;"> Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known results on rapid mi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1102.3635v1-abstract-full').style.display = 'inline'; document.getElementById('1102.3635v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1102.3635v1-abstract-full" style="display: none;"> Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known results on rapid mixing for the Tutte polynomial, the adjacency-rank ($R_2$-)polynomial and the interlace polynomial. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1102.3635v1-abstract-full').style.display = 'none'; document.getElementById('1102.3635v1-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> 17 February, 2011; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2011. </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">18 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05C85; 68R10; 60J10; 05C31; 68W20; 68W25 <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> G.2.2; F.2.2; G.3 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Electron. J. Combin. 21(4): #P4.19 (26 pp.), 2014 </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