Pascal Ochem

Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Alexandre Pinlou

Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Jeffrey Shallit

University of Waterloo

Mickaël Montassier

Centre National de la Recherche Scientifique

Narad Rampersad

University of Winnipeg

Louis Esperet

Laboratoire des Sciences pour la Conception, l'Optimisation et la Production

Matthieu Rosenfeld

Université de Montpellier

Daniel Gonçalves

Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Dieter Rautenbach

Universität Ulm

Stéphane Bessy

Université de Montpellier

Golnaz Badkobeh

Goldsmiths University of London

Cooperative Institutions

Centre National de la Recherche Scientifique

Université de Montpellier

Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Laboratoire Bordelais de Recherche en Informatique

Université de Bordeaux

Institut Polytechnique de Bordeaux

Hudson Institute

Institut national de recherche en informatique et en automatique

École Normale Supérieure de Lyon

University of Waterloo

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Vertex partitions of (C3,C4,C6)

Discrete Mathematics (2019)

François Dross Pascal Ochem

10.1016/j.disc.2019.07.002

Cite

Citations (2)

Repetition-free binary words of minimal density

Pascal Ochem

Repetition (rhetorical device)

Source

Cite

Citations (0)

On the interval number of special graphs

József Balogh Pascal Ochem András Pluhár

Interval graph

Source

Cite

Citations (0)

Avoiding conjugacy classes on the 5-letter alphabet

arXiv (Cornell University) (2018)

Golnaz Badkobeh Pascal Ochem

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]

10.48550/arxiv.1811.08231

Cite

Citations (0)

Avoidability of formulas with two variables

arXiv (Cornell University) (2016)

Pascal Ochem Matthieu Rosenfeld

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ of variables if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:\Delta^*\to\Sigma^*$ 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.

Morphism

Combinatorics on Words

Sigma

Source

Cite

Citations (2)

A generator of morphisms for infinite words

RAIRO - Theoretical Informatics and Applications (2006)

Pascal Ochem

We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne's thesis are 2-avoidable. We also prove that there exist exponentially many -free ternary words and -free 4-ary words. Finally we give small morphisms for binary words containing only the squares 2, 12 and (01)² and for binary words avoiding large squares and fractional repetitions.

Morphism

Combinatorics on Words

10.1051/ita:2006020

Cite

Citations (59)

Islands in Graphs on Surfaces

SIAM Journal on Discrete Mathematics (2016)

Louis Esperet Pascal Ochem

An island in a graph is a set $X$ of vertices such that each element of $X$ has few neighbors outside $X$. In this paper, we prove several bounds on the size of islands in large graphs embeddable on fixed surfaces. As direct consequences of our results, we obtain the following: (1) Every graph of genus $g$ can be colored from lists of size 5, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 3. (2) Every triangle-free graph of genus $g$ can be colored from lists of size 3, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 10. (3) Every graph of girth at least 6 and genus $g$ can be colored from lists of size 2, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 16. While (2) is optimal up to the size of the components, we conjecture that the size of the lists can be decreased to 4 in (1), and the girth can be decreased to 5 in (3). We also study the complexity of minimizing the size of monochromatic components in 2-colorings of planar graphs.

10.1137/140957883

Cite

Citations (25)

Some further results on squarefree arithmetic progressions in infinite words

arXiv (Cornell University) (2019)

James D. Currie Tero Harju Pascal Ochem Narad Rampersad

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.

Square-free integer

10.48550/arxiv.1901.06351

Cite

Citations (0)

Doubled patterns with reversal are 3-avoidable

arXiv (Cornell University) (2021)

Pascal Ochem

In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:\Delta^*\to\Sigma^*$ 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 \emph{doubled} if every variable occurs at least twice. Doubled patterns are known to be $3$-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, $h(V^R)$ is the mirror image of $h(V)$ for every $V\in\Delta$. We show that doubled patterns with reversal are $3$-avoidable.

Morphism

Sigma

Source

Cite

Citations (0)

Acyclic, Star, and Injective Colouring: Bounding the Diameter

The Electronic Journal of Combinatorics (2022)

Christoph Brause Petr A. Golovach Barnaby Martin Pascal Ochem Daniël Paulusma

We examine the effect of bounding the diameter for a number of natural and 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.

Star (game theory)

Bounding overwatch

Disjoint sets

10.37236/10738

Cite

Citations (7)