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–29 of 29 results for author: <span class="mathjax">Ochem, P</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=Ochem%2C+P">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="Ochem, P"> </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=Ochem%2C+P&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="Ochem, P"> <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/2311.13003">arXiv:2311.13003</a> <span> [<a href="https://arxiv.org/pdf/2311.13003">pdf</a>, <a href="https://arxiv.org/ps/2311.13003">ps</a>, <a href="https://arxiv.org/format/2311.13003">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"> Critical exponent of binary words with few distinct palindromes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dvo%C5%99%C3%A1kov%C3%A1%2C+L">L'ubom铆ra Dvo艡谩kov谩</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Opo%C4%8Densk%C3%A1%2C+D">Daniela Opo膷ensk谩</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="2311.13003v2-abstract-short" style="display: inline;"> We study infinite binary words that contain few distinct palindromes. In particular, we classify such words according to their critical exponents. This extends results by Fici and Zamboni [TCS 2013]. Interestingly, the words with 18 and 20 palindromes happen to be morphic images of the fixed point of the morphism $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{21}$,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.13003v2-abstract-full').style.display = 'inline'; document.getElementById('2311.13003v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2311.13003v2-abstract-full" style="display: none;"> We study infinite binary words that contain few distinct palindromes. In particular, we classify such words according to their critical exponents. This extends results by Fici and Zamboni [TCS 2013]. Interestingly, the words with 18 and 20 palindromes happen to be morphic images of the fixed point of the morphism $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{21}$, $\texttt{2}\mapsto\texttt{0}$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2311.13003v2-abstract-full').style.display = 'none'; document.getElementById('2311.13003v2-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> 25 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2301.03865">arXiv:2301.03865</a> <span> [<a href="https://arxiv.org/pdf/2301.03865">pdf</a>, <a href="https://arxiv.org/format/2301.03865">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</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.46298/dmtcs.10805">10.46298/dmtcs.10805 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Contact graphs of boxes with unidirectional contacts </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gon%C3%A7alves%2C+D">Daniel Gon莽alves</a>, <a href="/search/cs?searchtype=author&query=Limouzy%2C+V">Vincent Limouzy</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="2301.03865v4-abstract-short" style="display: inline;"> This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free. We give several structural properties of these graphs, and we raise several questions. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.03865v4-abstract-full" style="display: none;"> This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free. We give several structural properties of these graphs, and we raise several questions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.03865v4-abstract-full').style.display = 'none'; document.getElementById('2301.03865v4-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 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">Minor change</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Discrete Mathematics & Theoretical Computer Science, vol. 25:3 special issue ICGT'22, Special issues (May 17, 2024) dmtcs:10805 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2209.09598">arXiv:2209.09598</a> <span> [<a href="https://arxiv.org/pdf/2209.09598">pdf</a>, <a href="https://arxiv.org/ps/2209.09598">ps</a>, <a href="https://arxiv.org/format/2209.09598">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"> Complement Avoidance in Binary Words </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Currie%2C+J">James Currie</a>, <a href="/search/cs?searchtype=author&query=Dvo%C5%99akov%C3%A1%2C+L">L'ubom铆ra Dvo艡akov谩</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Opo%C4%8Densk%C3%A1%2C+D">Daniela Opo膷ensk谩</a>, <a href="/search/cs?searchtype=author&query=Rampersad%2C+N">Narad Rampersad</a>, <a href="/search/cs?searchtype=author&query=Shallit%2C+J">Jeffrey Shallit</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="2209.09598v2-abstract-short" style="display: inline;"> The complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. We study infinite binary words $\bf w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $\bf w$ then $\overline{x}$ is not a factor of $\bf w$. In particular, we classify such words according to their critical exponents. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2209.09598v2-abstract-full" style="display: none;"> The complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. We study infinite binary words $\bf w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $\bf w$ then $\overline{x}$ is not a factor of $\bf w$. In particular, we classify such words according to their critical exponents. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.09598v2-abstract-full').style.display = 'none'; document.getElementById('2209.09598v2-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 March, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2209.09223">arXiv:2209.09223</a> <span> [<a href="https://arxiv.org/pdf/2209.09223">pdf</a>, <a href="https://arxiv.org/format/2209.09223">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="Formal Languages and Automata Theory">cs.FL</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.46298/dmtcs.10063">10.46298/dmtcs.10063 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Antisquares and Critical Exponents </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Baranwal%2C+A">Aseem Baranwal</a>, <a href="/search/cs?searchtype=author&query=Currie%2C+J">James Currie</a>, <a href="/search/cs?searchtype=author&query=Mol%2C+L">Lucas Mol</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rampersad%2C+N">Narad Rampersad</a>, <a href="/search/cs?searchtype=author&query=Shallit%2C+J">Jeffrey Shallit</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="2209.09223v3-abstract-short" style="display: inline;"> The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.09223v3-abstract-full').style.display = 'inline'; document.getElementById('2209.09223v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2209.09223v3-abstract-full" style="display: none;"> The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is $\textit{good}$ if the only antisquares it contains are $01$ and $10$. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.09223v3-abstract-full').style.display = 'none'; document.getElementById('2209.09223v3-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> 24 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Combinatorics (September 6, 2023) dmtcs:10063 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2207.10171">arXiv:2207.10171</a> <span> [<a href="https://arxiv.org/pdf/2207.10171">pdf</a>, <a href="https://arxiv.org/format/2207.10171">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="Formal Languages and Automata Theory">cs.FL</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.46298/dmtcs.9919">10.46298/dmtcs.9919 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Pseudoperiodic Words and a Question of Shevelev </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Meleshko%2C+J">Joseph Meleshko</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Shallit%2C+J">Jeffrey Shallit</a>, <a href="/search/cs?searchtype=author&query=Shan%2C+S+L">Sonja Linghui Shan</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="2207.10171v3-abstract-short" style="display: inline;"> We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the sm… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2207.10171v3-abstract-full').style.display = 'inline'; document.getElementById('2207.10171v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2207.10171v3-abstract-full" style="display: none;"> We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2207.10171v3-abstract-full').style.display = 'none'; document.getElementById('2207.10171v3-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 October, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 July, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Automata, Logic and Semantics (October 16, 2023) dmtcs:9919 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.01776">arXiv:2206.01776</a> <span> [<a href="https://arxiv.org/pdf/2206.01776">pdf</a>, <a href="https://arxiv.org/format/2206.01776">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Formal Languages and Automata Theory">cs.FL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Dynamical Systems">math.DS</span> </div> </div> <p class="title is-5 mathjax"> Properties of a Ternary Infinite Word </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Currie%2C+J">James Currie</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rampersad%2C+N">Narad Rampersad</a>, <a href="/search/cs?searchtype=author&query=Shallit%2C+J">Jeffrey Shallit</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="2206.01776v1-abstract-short" style="display: inline;"> We study the properties of the ternary infinite word p = 012102101021012101021012 ... , that is, the fixed point of the map h:0->01, 1->21, 2->0. We determine its factor complexity, critical exponent, and prove that it is 2-balanced. We compute its abelian complexity and determine the lengths of its bispecial factors. Finally, we give a characterization of p in terms of avoided factors. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.01776v1-abstract-full" style="display: none;"> We study the properties of the ternary infinite word p = 012102101021012101021012 ... , that is, the fixed point of the map h:0->01, 1->21, 2->0. We determine its factor complexity, critical exponent, and prove that it is 2-balanced. We compute its abelian complexity and determine the lengths of its bispecial factors. Finally, we give a characterization of p in terms of avoided factors. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.01776v1-abstract-full').style.display = 'none'; document.getElementById('2206.01776v1-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 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2104.10593">arXiv:2104.10593</a> <span> [<a href="https://arxiv.org/pdf/2104.10593">pdf</a>, <a href="https://arxiv.org/ps/2104.10593">ps</a>, <a href="https://arxiv.org/format/2104.10593">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="Computational Complexity">cs.CC</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="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Acyclic, Star, and Injective Colouring: Bounding the Diameter </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Brause%2C+C">Christoph Brause</a>, <a href="/search/cs?searchtype=author&query=Golovach%2C+P">Petr Golovach</a>, <a href="/search/cs?searchtype=author&query=Martin%2C+B">Barnaby Martin</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Paulusma%2C+D">Dani毛l Paulusma</a>, <a href="/search/cs?searchtype=author&query=Smith%2C+S">Siani Smith</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="2104.10593v4-abstract-short" style="display: inline;"> We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as $L(1,1)$-Labell… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2104.10593v4-abstract-full').style.display = 'inline'; document.getElementById('2104.10593v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2104.10593v4-abstract-full" style="display: none;"> We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as $L(1,1)$-Labelling and we also consider the framework of $L(a,b)$-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most $d$, Acyclic $3$-Colouring is polynomial-time solvable if $d\leq 2$ but NP-complete if $d\geq 4$, and Star $3$-Colouring is polynomial-time solvable if $d\leq 3$ but NP-complete for $d\geq 8$. As far as we are aware, Star $3$-Colouring is the first problem that exhibits a complexity jump for some $d\geq 3$. Our third main result is that $L(1,2)$-Labelling is NP-complete for graphs of diameter $2$; we relate the latter problem to a special case of Hamiltonian Path. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2104.10593v4-abstract-full').style.display = 'none'; document.getElementById('2104.10593v4-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> 8 September, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 April, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2008.09415">arXiv:2008.09415</a> <span> [<a href="https://arxiv.org/pdf/2008.09415">pdf</a>, <a href="https://arxiv.org/format/2008.09415">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bok%2C+J">Jan Bok</a>, <a href="/search/cs?searchtype=author&query=Jedlickova%2C+N">Nikola Jedlickova</a>, <a href="/search/cs?searchtype=author&query=Martin%2C+B">Barnaby Martin</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Paulusma%2C+D">Daniel Paulusma</a>, <a href="/search/cs?searchtype=author&query=Smith%2C+S">Siani Smith</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="2008.09415v5-abstract-short" style="display: inline;"> A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.09415v5-abstract-full').style.display = 'inline'; document.getElementById('2008.09415v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2008.09415v5-abstract-full" style="display: none;"> A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as $L(1,1)$-Labelling). A classical complexity result on Colouring is a well-known dichotomy for $H$-free graphs (a graph is $H$-free if it does not contain $H$ as an induced subgraph). In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We perform such a study and give almost complete complexity classifications for Acyclic Colouring, Star Colouring and Injective Colouring on $H$-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours $k$ is fixed, that is, not part of the input. From our study it follows that for fixed $k$ the three problems behave in the same way, but this is no longer true if $k$ is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.09415v5-abstract-full').style.display = 'none'; document.getElementById('2008.09415v5-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 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 August, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 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">Extended abstracts appeared / will appear at ESA 2020 and CSR 2021</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1907.03266">arXiv:1907.03266</a> <span> [<a href="https://arxiv.org/pdf/1907.03266">pdf</a>, <a href="https://arxiv.org/ps/1907.03266">ps</a>, <a href="https://arxiv.org/format/1907.03266">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="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</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.1016/j.dam.2020.03.029">10.1016/j.dam.2020.03.029 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Complexity of planar signed graph homomorphisms to cycles </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dross%2C+F">Fran莽ois Dross</a>, <a href="/search/cs?searchtype=author&query=Foucaud%2C+F">Florent Foucaud</a>, <a href="/search/cs?searchtype=author&query=Mitsou%2C+V">Valia Mitsou</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Pierron%2C+T">Th茅o Pierron</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="1907.03266v2-abstract-short" style="display: inline;"> We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1907.03266v2-abstract-full').style.display = 'inline'; document.getElementById('1907.03266v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1907.03266v2-abstract-full" style="display: none;"> We study homomorphism problems of signed graphs. A signed graph is an undirected graph where each edge is given a sign, positive or negative. An important concept for signed graphs is the operation of switching at a vertex, which is to change the sign of each incident edge. A homomorphism of a graph is a vertex-mapping that preserves the adjacencies; in the case of signed graphs, we also preserve the edge-signs. Special homomorphisms of signed graphs, called s-homomorphisms, have been studied. In an s-homomorphism, we allow, before the mapping, to perform any number of switchings on the source signed graph. This concept has been extensively studied, and a full complexity classification (polynomial or NP-complete) for s-homomorphism to a fixed target signed graph has recently been obtained. Such a dichotomy is not known when we restrict the input graph to be planar (not even for non-signed graph homomorphisms). We show that deciding whether a (non-signed) planar graph admits a homomorphism to the square $C_t^2$ of a cycle with $t\ge 6$, or to the circular clique $K_{4t/(2t-1)}$ with $t\ge2$, are NP-complete problems. We use these results to show that deciding whether a planar signed graph admits an s-homomorphism to an unbalanced even cycle is NP-complete. (A cycle is unbalanced if it has an odd number of negative edges). We deduce a complete complexity dichotomy for the planar s-homomorphism problem with any signed cycle as a target. We also study further restrictions involving the maximum degree and the girth of the input signed graph. We prove that planar s-homomorphism problems to signed cycles remain NP-complete even for inputs of maximum degree~$3$ (except for the case of unbalanced $4$-cycles, for which we show this for maximum degree~$4$). We also show that for a given integer $g$, the problem for signed bipartite planar inputs of girth $g$ is either trivial or NP-complete. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1907.03266v2-abstract-full').style.display = 'none'; document.getElementById('1907.03266v2-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 July, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 July, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 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">17 pages, 10 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Discrete Applied Mathematics 284:166-178, 2020 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1905.12484">arXiv:1905.12484</a> <span> [<a href="https://arxiv.org/pdf/1905.12484">pdf</a>, <a href="https://arxiv.org/format/1905.12484">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Oriented coloring of graphs with low maximum degree </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Pinlou%2C+A">Alexandre Pinlou</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.12484v1-abstract-short" style="display: inline;"> Duffy et al. [C. Duffy, G. MacGillivray, and 脡. Sopena, Oriented colourings of graphs with maximum degree three and four, Discrete Mathematics, 342(4), p. 959--974, 2019] recently considered the oriented chromatic number of connected oriented graphs with maximum degree $3$ and $4$, proving it is at most $9$ and $69$, respectively. In this paper, we improve these results by showing that the oriente… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.12484v1-abstract-full').style.display = 'inline'; document.getElementById('1905.12484v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1905.12484v1-abstract-full" style="display: none;"> Duffy et al. [C. Duffy, G. MacGillivray, and 脡. Sopena, Oriented colourings of graphs with maximum degree three and four, Discrete Mathematics, 342(4), p. 959--974, 2019] recently considered the oriented chromatic number of connected oriented graphs with maximum degree $3$ and $4$, proving it is at most $9$ and $69$, respectively. In this paper, we improve these results by showing that the oriented chromatic number of non-necessarily connected oriented graphs with maximum degree $3$ (resp. $4$) is at most $9$ (resp. $26$). The bound of $26$ actually follows from a general result which determines properties of a target graph to be universal for graphs of bounded maximum degree. This generalization also allows us to get the upper bound of $90$ (resp. $306$, $1322$) for the oriented chromatic number of graphs with maximum degree $5$ (resp. $6$, $7$). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.12484v1-abstract-full').style.display = 'none'; document.getElementById('1905.12484v1-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> 29 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1905.02123">arXiv:1905.02123</a> <span> [<a href="https://arxiv.org/pdf/1905.02123">pdf</a>, <a href="https://arxiv.org/format/1905.02123">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Partitioning sparse graphs into an independent set and a graph with bounded size components </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Choi%2C+I">Ilkyoo Choi</a>, <a href="/search/cs?searchtype=author&query=Dross%2C+F">Fran莽ois Dross</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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.02123v1-abstract-short" style="display: inline;"> We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph $G$ admits an $({\cal I}, {\cal O}_k)$-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.02123v1-abstract-full').style.display = 'inline'; document.getElementById('1905.02123v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1905.02123v1-abstract-full" style="display: none;"> We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph $G$ admits an $({\cal I}, {\cal O}_k)$-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most $k$. We prove that every graph $G$ with $\operatorname{mad}(G)<\frac 52$ admits an $({\cal I}, {\cal O}_3)$-partition. This implies that every planar graph with girth at least $10$ can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph $G$ with $\operatorname{mad}(G) < \frac{8k}{3k+1} = \frac{8}{3}\left( 1 - \frac{1}{3k+1} \right)$ admits an $({\cal I}, {\cal O}_k)$-partition. This implies that every planar graph with girth at least $9$ can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 9. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.02123v1-abstract-full').style.display = 'none'; document.getElementById('1905.02123v1-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 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1904.09157">arXiv:1904.09157</a> <span> [<a href="https://arxiv.org/pdf/1904.09157">pdf</a>, <a href="https://arxiv.org/ps/1904.09157">ps</a>, <a href="https://arxiv.org/format/1904.09157">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Formal Languages and Automata Theory">cs.FL</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="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> New results on pseudosquare avoidance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ng%2C+T">Tim Ng</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rampersad%2C+N">Narad Rampersad</a>, <a href="/search/cs?searchtype=author&query=Shallit%2C+J">Jeffrey Shallit</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="1904.09157v1-abstract-short" style="display: inline;"> We start by considering binary words containing the minimum possible numbers of squares and antisquares (where an antisquare is a word of the form $x \overline{x}$), and we completely classify which possibilities can occur. We consider avoiding $x p(x)$, where $p$ is any permutation of the underlying alphabet, and $x t(x)$, where $t$ is any transformation of the underlying alphabet. Finally, we pr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1904.09157v1-abstract-full').style.display = 'inline'; document.getElementById('1904.09157v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1904.09157v1-abstract-full" style="display: none;"> We start by considering binary words containing the minimum possible numbers of squares and antisquares (where an antisquare is a word of the form $x \overline{x}$), and we completely classify which possibilities can occur. We consider avoiding $x p(x)$, where $p$ is any permutation of the underlying alphabet, and $x t(x)$, where $t$ is any transformation of the underlying alphabet. Finally, we prove the existence of an infinite binary word simultaneously avoiding all occurrences of $x h(x)$ for every nonerasing morphism $h$ and all sufficiently large words $x$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1904.09157v1-abstract-full').style.display = 'none'; document.getElementById('1904.09157v1-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 April, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.06351">arXiv:1901.06351</a> <span> [<a href="https://arxiv.org/pdf/1901.06351">pdf</a>, <a href="https://arxiv.org/format/1901.06351">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="Formal Languages and Automata Theory">cs.FL</span> </div> </div> <p class="title is-5 mathjax"> Some further results on squarefree arithmetic progressions in infinite words </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Currie%2C+J">James Currie</a>, <a href="/search/cs?searchtype=author&query=Harju%2C+T">Tero Harju</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rampersad%2C+N">Narad Rampersad</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="1901.06351v1-abstract-short" style="display: inline;"> In a recent paper, one of us posed three open problems concerning squarefree arithmetic progressions in infinite words. In this note we solve these problems and prove some additional results. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06351v1-abstract-full" style="display: none;"> In a recent paper, one of us posed three open problems concerning squarefree arithmetic progressions in infinite words. In this note we solve these problems and prove some additional results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06351v1-abstract-full').style.display = 'none'; document.getElementById('1901.06351v1-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 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">13 pages, 2 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68R15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1811.08231">arXiv:1811.08231</a> <span> [<a href="https://arxiv.org/pdf/1811.08231">pdf</a>, <a href="https://arxiv.org/ps/1811.08231">ps</a>, <a href="https://arxiv.org/format/1811.08231">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"> Avoiding conjugacy classes on the 5-letter alphabet </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Badkobeh%2C+G">Golnaz Badkobeh</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1811.08231v1-abstract-short" style="display: inline;"> We construct an infinite word $w$ over the $5$-letter alphabet such that for every factor $f$ of $w$ of length at least two, there exists a cyclic permutation of $f$ that is not a factor of $w$. In other words, $w$ does not contain a non-trivial conjugacy class. This proves the conjecture in Gamard et al. [TCS 2018] </span> <span class="abstract-full has-text-grey-dark mathjax" id="1811.08231v1-abstract-full" style="display: none;"> We construct an infinite word $w$ over the $5$-letter alphabet such that for every factor $f$ of $w$ of length at least two, there exists a cyclic permutation of $f$ that is not a factor of $w$. In other words, $w$ does not contain a non-trivial conjugacy class. This proves the conjecture in Gamard et al. [TCS 2018] <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1811.08231v1-abstract-full').style.display = 'none'; document.getElementById('1811.08231v1-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> 20 November, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1809.01426">arXiv:1809.01426</a> <span> [<a href="https://arxiv.org/pdf/1809.01426">pdf</a>, <a href="https://arxiv.org/ps/1809.01426">ps</a>, <a href="https://arxiv.org/format/1809.01426">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Repetition avoidance in products of factors </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fleischmann%2C+P">Pamela Fleischmann</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Reshadi%2C+K">Kamellia Reshadi</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="1809.01426v2-abstract-short" style="display: inline;"> We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let $\texttt{pexp}_i(w)$ be the supremum of the exponent over the products of $i$ factors of the word $w$. The repetition threshold $\texttt{RT}_i(k)$ is then the infimum of $\texttt{pexp}_i(w)$ over all words $w\in危^蠅_k$. Mousavi and Shallit obtained th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1809.01426v2-abstract-full').style.display = 'inline'; document.getElementById('1809.01426v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1809.01426v2-abstract-full" style="display: none;"> We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let $\texttt{pexp}_i(w)$ be the supremum of the exponent over the products of $i$ factors of the word $w$. The repetition threshold $\texttt{RT}_i(k)$ is then the infimum of $\texttt{pexp}_i(w)$ over all words $w\in危^蠅_k$. Mousavi and Shallit obtained that $\texttt{RT}_i(2)=2i$ and $\texttt{RT}_2(3)=\tfrac{13}4$. We show that $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac14$ if $i$ is even and $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac16$ if $i$ is odd and $i\ge3$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1809.01426v2-abstract-full').style.display = 'none'; document.getElementById('1809.01426v2-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> 27 April, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 September, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1711.08710">arXiv:1711.08710</a> <span> [<a href="https://arxiv.org/pdf/1711.08710">pdf</a>, <a href="https://arxiv.org/format/1711.08710">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Vertex partitions of $(C_3,C_4,C_6)$-free planar graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dross%2C+F">Fran莽ois Dross</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1711.08710v1-abstract-short" style="display: inline;"> A graph is $(k_1,k_2)$-colorable if its vertex set can be partitioned into a graph with maximum degree at most $k_1$ and and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1711.08710v1-abstract-full" style="display: none;"> A graph is $(k_1,k_2)$-colorable if its vertex set can be partitioned into a graph with maximum degree at most $k_1$ and and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1711.08710v1-abstract-full').style.display = 'none'; document.getElementById('1711.08710v1-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> 23 November, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1706.03233">arXiv:1706.03233</a> <span> [<a href="https://arxiv.org/pdf/1706.03233">pdf</a>, <a href="https://arxiv.org/ps/1706.03233">ps</a>, <a href="https://arxiv.org/format/1706.03233">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> On some interesting ternary formulas </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rosenfeld%2C+M">Matthieu Rosenfeld</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="1706.03233v2-abstract-short" style="display: inline;"> We obtain the following results about the avoidance of ternary formulas. Up to renaming of the letters, the only infinite ternary words avoiding the formula $ABCAB.ABCBA.ACB.BAC$ (resp. $ABCA.BCAB.BCB.CBA$) have the same set of recurrent factors as the fixed point of $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. The formula $ABAC.BACA.ABCA$ is avoi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1706.03233v2-abstract-full').style.display = 'inline'; document.getElementById('1706.03233v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1706.03233v2-abstract-full" style="display: none;"> We obtain the following results about the avoidance of ternary formulas. Up to renaming of the letters, the only infinite ternary words avoiding the formula $ABCAB.ABCBA.ACB.BAC$ (resp. $ABCA.BCAB.BCB.CBA$) have the same set of recurrent factors as the fixed point of $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. The formula $ABAC.BACA.ABCA$ is avoided by polynomially many binary words and there exist arbitrarily many infinite binary words with different sets of recurrent factors that avoid it. If every variable of a ternary formula appears at least twice in the same fragment, then the formula is $3$-avoidable. The pattern $ABACADABCA$ is unavoidable for the class of $C_4$-minor-free graphs with maximum degree~$3$. This disproves a conjecture of Grytczuk. The formula $ABCA.ACBA$, or equivalently the palindromic pattern $ABCADACBA$, has avoidability index $4$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1706.03233v2-abstract-full').style.display = 'none'; document.getElementById('1706.03233v2-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> 25 September, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 June, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2017. </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">Version 1 was accepted to WORDS 2017. Version 2 contains new results in section 4 (about nice formulas) and section 6 (about palindromic patterns)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.01283">arXiv:1702.01283</a> <span> [<a href="https://arxiv.org/pdf/1702.01283">pdf</a>, <a href="https://arxiv.org/format/1702.01283">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> 2-subcoloring is NP-complete for planar comparability graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1702.01283v1-abstract-short" style="display: inline;"> A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01283v1-abstract-full').style.display = 'inline'; document.getElementById('1702.01283v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.01283v1-abstract-full" style="display: none;"> A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring is also NP-complete for planar comparability graphs with maximum degree 4. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01283v1-abstract-full').style.display = 'none'; document.getElementById('1702.01283v1-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 February, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.01058">arXiv:1702.01058</a> <span> [<a href="https://arxiv.org/pdf/1702.01058">pdf</a>, <a href="https://arxiv.org/format/1702.01058">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> On repetition thresholds of caterpillars and trees of bounded degree </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Lu%C5%BEar%2C+B">Borut Lu啪ar</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Pinlou%2C+A">Alexandre Pinlou</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="1702.01058v1-abstract-short" style="display: inline;"> The repetition threshold is the smallest real number $伪$ such that there exists an infinite word over a $k$-letter alphabet that avoids repetition of exponent strictly greater than $伪$. This notion can be generalized to graph classes. In this paper, we completely determine the repetition thresholds for caterpillars and caterpillars of maximum degree $3$. Additionally, we present bounds for the rep… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01058v1-abstract-full').style.display = 'inline'; document.getElementById('1702.01058v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.01058v1-abstract-full" style="display: none;"> The repetition threshold is the smallest real number $伪$ such that there exists an infinite word over a $k$-letter alphabet that avoids repetition of exponent strictly greater than $伪$. This notion can be generalized to graph classes. In this paper, we completely determine the repetition thresholds for caterpillars and caterpillars of maximum degree $3$. Additionally, we present bounds for the repetition thresholds of trees with bounded maximum degrees. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01058v1-abstract-full').style.display = 'none'; document.getElementById('1702.01058v1-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 February, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68R05 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Electron J. Combin. 25 (2018), #P1.61 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1610.04439">arXiv:1610.04439</a> <span> [<a href="https://arxiv.org/pdf/1610.04439">pdf</a>, <a href="https://arxiv.org/ps/1610.04439">ps</a>, <a href="https://arxiv.org/format/1610.04439">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Avoidability of circular formulas </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gamard%2C+G">Guilhem Gamard</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Richomme%2C+G">Gwena毛l Richomme</a>, <a href="/search/cs?searchtype=author&query=S%C3%A9%C3%A9bold%2C+P">Patrice S茅茅bold</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="1610.04439v1-abstract-short" style="display: inline;"> Clark has defined the notion of $n$-avoidance basis which contains the avoidable formulas with at most $n$ variables that are closest to be unavoidable in some sense. The family $C_i$ of circular formulas is such that $C_1=AA$, $C_2=ABA.BAB$, $C_3=ABCA.BCAB.CABC$ and so on. For every $i\le n$, the $n$-avoidance basis contains $C_i$. Clark showed that the avoidability index of every circular formul… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1610.04439v1-abstract-full').style.display = 'inline'; document.getElementById('1610.04439v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1610.04439v1-abstract-full" style="display: none;"> Clark has defined the notion of $n$-avoidance basis which contains the avoidable formulas with at most $n$ variables that are closest to be unavoidable in some sense. The family $C_i$ of circular formulas is such that $C_1=AA$, $C_2=ABA.BAB$, $C_3=ABCA.BCAB.CABC$ and so on. For every $i\le n$, the $n$-avoidance basis contains $C_i$. Clark showed that the avoidability index of every circular formula and of every formula in the $3$-avoidance basis (and thus of every avoidable formula containing at most 3 variables) is at most 4. We determine exactly the avoidability index of these formulas. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1610.04439v1-abstract-full').style.display = 'none'; document.getElementById('1610.04439v1-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> 14 October, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1606.03955">arXiv:1606.03955</a> <span> [<a href="https://arxiv.org/pdf/1606.03955">pdf</a>, <a href="https://arxiv.org/format/1606.03955">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Formal Languages and Automata Theory">cs.FL</span> </div> </div> <p class="title is-5 mathjax"> Avoidability of formulas with two variables </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Rosenfeld%2C+M">Matthieu Rosenfeld</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="1606.03955v2-abstract-short" style="display: inline;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ of variables if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We consider the patterns such that at most two variables a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1606.03955v2-abstract-full').style.display = 'inline'; document.getElementById('1606.03955v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1606.03955v2-abstract-full" style="display: none;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ of variables if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We consider the patterns such that at most two variables appear at least twice, or equivalently, the formulas with at most two variables. For each such formula, we determine whether it is $2$-avoidable, and if it is $2$-avoidable, we determine whether it is avoided by exponentially many binary words. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1606.03955v2-abstract-full').style.display = 'none'; document.getElementById('1606.03955v2-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> 13 October, 2016; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 13 June, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1512.02207">arXiv:1512.02207</a> <span> [<a href="https://arxiv.org/pdf/1512.02207">pdf</a>, <a href="https://arxiv.org/format/1512.02207">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> The complexity of partitioning into disjoint cliques and a triangle-free graph </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bougeret%2C+M">Marin Bougeret</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1512.02207v1-abstract-short" style="display: inline;"> Motivated by Chudnovsky's structure theorem of bull-free graphs, Abu-Khzam, Feghali, and M眉ller have recently proved that deciding if a graph has a vertex partition into disjoint cliques and a triangle-free graph is NP-complete for five graph classes. The problem is trivial for the intersection of these five classes. We prove that the problem is NP-complete for the intersection of two subsets of s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.02207v1-abstract-full').style.display = 'inline'; document.getElementById('1512.02207v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1512.02207v1-abstract-full" style="display: none;"> Motivated by Chudnovsky's structure theorem of bull-free graphs, Abu-Khzam, Feghali, and M眉ller have recently proved that deciding if a graph has a vertex partition into disjoint cliques and a triangle-free graph is NP-complete for five graph classes. The problem is trivial for the intersection of these five classes. We prove that the problem is NP-complete for the intersection of two subsets of size four among the five classes. We also show NP-completeness for other small classes, such as graphs with maximum degree 4 and line graphs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.02207v1-abstract-full').style.display = 'none'; document.getElementById('1512.02207v1-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> 7 December, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1510.01753">arXiv:1510.01753</a> <span> [<a href="https://arxiv.org/pdf/1510.01753">pdf</a>, <a href="https://arxiv.org/ps/1510.01753">ps</a>, <a href="https://arxiv.org/format/1510.01753">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Doubled patterns are $3$-avoidable </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1510.01753v1-abstract-short" style="display: inline;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. A pattern is said to be doubled if no variable occurs only once. Double… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1510.01753v1-abstract-full').style.display = 'inline'; document.getElementById('1510.01753v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1510.01753v1-abstract-full" style="display: none;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. A pattern is said to be doubled if no variable occurs only once. Doubled patterns with at most 3 variables and patterns with at least 6 variables are $3$-avoidable. We show that doubled patterns with 4 and 5 variables are also $3$-avoidable. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1510.01753v1-abstract-full').style.display = 'none'; document.getElementById('1510.01753v1-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 October, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1401.3308">arXiv:1401.3308</a> <span> [<a href="https://arxiv.org/pdf/1401.3308">pdf</a>, <a href="https://arxiv.org/ps/1401.3308">ps</a>, <a href="https://arxiv.org/format/1401.3308">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Homomorphisms of signed planar graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Pinlou%2C+A">Alexandre Pinlou</a>, <a href="/search/cs?searchtype=author&query=Sen%2C+S">Sagnik Sen</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="1401.3308v1-abstract-short" style="display: inline;"> Signed graphs are studied since the middle of the last century. Recently, the notion of homomorphism of signed graphs has been introduced since this notion captures a number of well known conjectures which can be reformulated using the definitions of signed homomorphism. In this paper, we introduce and study the properties of some target graphs for signed homomorphism. Using these properties, we… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.3308v1-abstract-full').style.display = 'inline'; document.getElementById('1401.3308v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1401.3308v1-abstract-full" style="display: none;"> Signed graphs are studied since the middle of the last century. Recently, the notion of homomorphism of signed graphs has been introduced since this notion captures a number of well known conjectures which can be reformulated using the definitions of signed homomorphism. In this paper, we introduce and study the properties of some target graphs for signed homomorphism. Using these properties, we obtain upper bounds on the signed chromatic numbers of graphs with bounded acyclic chromatic number and of signed planar graphs with given girth. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.3308v1-abstract-full').style.display = 'none'; document.getElementById('1401.3308v1-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> 14 January, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2014. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1301.4682">arXiv:1301.4682</a> <span> [<a href="https://arxiv.org/pdf/1301.4682">pdf</a>, <a href="https://arxiv.org/ps/1301.4682">ps</a>, <a href="https://arxiv.org/format/1301.4682">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Formal Languages and Automata Theory">cs.FL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</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.1051/ita/2014015">10.1051/ita/2014015 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Binary Patterns in Binary Cube-Free Words: Avoidability and Growth </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Mercas%2C+R">Robert Mercas</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Samsonov%2C+A+V">Alexei V. Samsonov</a>, <a href="/search/cs?searchtype=author&query=Shur%2C+A+M">Arseny M. Shur</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="1301.4682v1-abstract-short" style="display: inline;"> The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth r… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.4682v1-abstract-full').style.display = 'inline'; document.getElementById('1301.4682v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1301.4682v1-abstract-full" style="display: none;"> The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.4682v1-abstract-full').style.display = 'none'; document.getElementById('1301.4682v1-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> 20 January, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2013. </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, 2 tables; submitted to RAIRO TIA (Special issue of Mons Days 2012)</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68R15 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> RAIRO-Theor. Inf. Appl. 48 (2014) 369-389 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1301.1873">arXiv:1301.1873</a> <span> [<a href="https://arxiv.org/pdf/1301.1873">pdf</a>, <a href="https://arxiv.org/ps/1301.1873">ps</a>, <a href="https://arxiv.org/format/1301.1873">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Application of entropy compression in pattern avoidance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Pinlou%2C+A">Alexandre Pinlou</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="1301.1873v1-abstract-short" style="display: inline;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ if there is no factor $f$ of $w$ such that $f= (p)$ where $h: 螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebra… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.1873v1-abstract-full').style.display = 'inline'; document.getElementById('1301.1873v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1301.1873v1-abstract-full" style="display: none;"> In combinatorics on words, a word $w$ over an alphabet $危$ is said to avoid a pattern $p$ over an alphabet $螖$ if there is no factor $f$ of $w$ such that $f= (p)$ where $h: 螖^*\to危^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.1873v1-abstract-full').style.display = 'none'; document.getElementById('1301.1873v1-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 January, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2013. </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</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68R15 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1201.0043">arXiv:1201.0043</a> <span> [<a href="https://arxiv.org/pdf/1201.0043">pdf</a>, <a href="https://arxiv.org/ps/1201.0043">ps</a>, <a href="https://arxiv.org/format/1201.0043">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> The Maximum Clique Problem in Multiple Interval Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Francis%2C+M+C">Mathew C. Francis</a>, <a href="/search/cs?searchtype=author&query=Gon%C3%A7alves%2C+D">Daniel Gon莽alves</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="1201.0043v2-abstract-short" style="display: inline;"> Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1201.0043v2-abstract-full').style.display = 'inline'; document.getElementById('1201.0043v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1201.0043v2-abstract-full" style="display: none;"> Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $t\geq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $t\geq 4$ and polynomial-time solvable when $t\leq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1201.0043v2-abstract-full').style.display = 'none'; document.getElementById('1201.0043v2-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 March, 2012; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 December, 2011; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2012. </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">22 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/1010.5624">arXiv:1010.5624</a> <span> [<a href="https://arxiv.org/pdf/1010.5624">pdf</a>, <a href="https://arxiv.org/ps/1010.5624">ps</a>, <a href="https://arxiv.org/format/1010.5624">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</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"> Locally identifying coloring of graphs </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=Gravier%2C+S">Sylvain Gravier</a>, <a href="/search/cs?searchtype=author&query=Montassier%2C+M">Mickael Montassier</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</a>, <a href="/search/cs?searchtype=author&query=Parreau%2C+A">Aline Parreau</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="1010.5624v2-abstract-short" style="display: inline;"> We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring c of a graph G is said to be locally identifying, if for any adjacent vertices u and v with distinct closed neighborhood, the sets of colors that appear in the closed neighborhood of u and v are distinct. Let $蠂_{lid}(G)$ be the minimum number of colors used in a locally identifying vertex-coloring of G. I… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1010.5624v2-abstract-full').style.display = 'inline'; document.getElementById('1010.5624v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1010.5624v2-abstract-full" style="display: none;"> We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring c of a graph G is said to be locally identifying, if for any adjacent vertices u and v with distinct closed neighborhood, the sets of colors that appear in the closed neighborhood of u and v are distinct. Let $蠂_{lid}(G)$ be the minimum number of colors used in a locally identifying vertex-coloring of G. In this paper, we give several bounds on $蠂_{lid}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $蠂_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1010.5624v2-abstract-full').style.display = 'none'; document.getElementById('1010.5624v2-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 May, 2012; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 October, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2010. </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">21 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Electron. J. Combin. 19(2) (2012), #P40 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0906.4750">arXiv:0906.4750</a> <span> [<a href="https://arxiv.org/pdf/0906.4750">pdf</a>, <a href="https://arxiv.org/ps/0906.4750">ps</a>, <a href="https://arxiv.org/format/0906.4750">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> On maximal repetitions of arbitrary exponent </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Kolpakov%2C+R">Roman Kolpakov</a>, <a href="/search/cs?searchtype=author&query=Kucherov%2C+G">Gregory Kucherov</a>, <a href="/search/cs?searchtype=author&query=Ochem%2C+P">Pascal Ochem</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="0906.4750v1-abstract-short" style="display: inline;"> The first two authors have shown [KK99,KK00] that the sum the exponent (and thus the number) of maximal repetitions of exponent at least 2 (also called runs) is linear in the length of the word. The exponent 2 in the definition of a run may seem arbitrary. In this paper, we consider maximal repetitions of exponent strictly greater than 1. </span> <span class="abstract-full has-text-grey-dark mathjax" id="0906.4750v1-abstract-full" style="display: none;"> The first two authors have shown [KK99,KK00] that the sum the exponent (and thus the number) of maximal repetitions of exponent at least 2 (also called runs) is linear in the length of the word. The exponent 2 in the definition of a run may seem arbitrary. In this paper, we consider maximal repetitions of exponent strictly greater than 1. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0906.4750v1-abstract-full').style.display = 'none'; document.getElementById('0906.4750v1-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> 25 June, 2009; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2009. </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">8 pages, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> G.2.1 </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