BZPEER

preprint2022arXiv

Doubled patterns with reversal and square-free doubled patterns

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 \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Δ$ . We show that doubled patterns with reversal are $3$ -avoidable. We also conjecture that (classical) doubled patterns that do not contain a square are $2$ -avoidable. We confirm this conjecture for patterns with at most 4 variables. This implies that for every doubled pattern $p$ , the growth rate of ternary words avoiding $p$ is at least the growth rate of ternary square-free words. A previous version of this paper containing only the first result has been presented at WORDS 2021.

preprint2022arXiv

Properties of a Ternary Infinite Word

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.

preprint2020arXiv

Homomorphisms of planar $(m, n)$ -colored-mixed graphs to planar targets

An $(m, n)$ -colored-mixed graph $G=(V, A_1, A_2,\cdots, A_m, E_1, E_2,\cdots, E_n)$ is a graph having $m$ colors of arcs and $n$ colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$ -colored-mixed graph $G$ to another $(m, n)$ -colored-mixed graph $H$ is a morphism $φ:V(G)\rightarrow V(H)$ such that each edge (resp. arc) of $G$ is mapped to an edge (resp. arc) of $H$ of the same color (and orientation). An $(m,n)$ -colored-mixed graph $T$ is said to be $P_g^{(m, n)}$ -universal if every graph in $P_g^{(m, n)}$ (the planar $(m, n)$ -colored-mixed graphs with girth at least $g$ ) admits a homomorphism to $T$ . We show that planar $P_g^{(m, n)}$ -universal graphs do not exist for $2m+n\ge3$ (and any value of $g$ ) and find a minimal (in the number vertices) planar $P_g^{(m, n)}$ -universal graphs in the other cases.

preprint2020arXiv

Nice formulas, $xyx$ -formulas, and palindrome patterns

We characterize the formulas that are avoided by every $α$ -free word for some $α>1$ . We study the avoidability index of formulas whose fragments are of the form $XYX$ . The largest avoidability index of an avoidable palindrome pattern is known to be at least $4$ and at most $16$ . We make progress toward the conjecture that every avoidable palindrome pattern is $4$ -avoidable.

preprint2018arXiv

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

A $d$ -subsequence of a sequence $φ= x_1\dots x_n$ is a subsequence $x_i x_{i+d} x_{i+2d} \dots$ , for any positive integer $d$ and any $i$ , $1 \le i \le n$ . A \textit{ $k$ -Thue sequence} is a sequence in which every $d$ -subsequence, for $1 \le d \le k$ , is non-repetitive, i.e. it contains no consecutive equal subsequences. In 2002, Grytczuk proposed a conjecture that for any $k$ , $k+2$ symbols are enough to construct a $k$ -Thue sequences of arbitrary lengths. So far, the conjecture has been confirmed for $k \in \{1,2,3,5\}$ . Here, we present two different proving techniques, and confirm it for all $k$ , with $2 \le k \le 8$ .

preprint2016arXiv

Avoidability of circular formulas

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.

preprint2016arXiv

Avoidability of formulas with two variables

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.

preprint2015arXiv

Bounds on the Exponential Domination Number

As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if $S$ is a set of vertices of a graph $G$ , then $S$ is an exponential dominating set of $G$ if $\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}\geq 1$ for every vertex $u$ in $V(G)\setminus S$ , where ${\rm dist}_{(G,S)}(u,v)$ is the distance between $u\in V(G)\setminus S$ and $v\in S$ in the graph $G-(S\setminus \{ v\})$ . The exponential domination number $γ_e(G)$ of $G$ is the minimum order of an exponential dominating set of $G$ . Dankelmann et al. show $\frac{1}{4}({\rm d}+2)\leq γ_e(G)\leq \frac{2}{5}(n+2)$ for a connected graph $G$ of order $n$ and diameter ${\rm d}$ . We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph $G$ of order $n$ , maximum degree $Δ$ at least $3$ , radius ${\rm r}$ at least $1$ , we show \begin{eqnarray*} γ_e(G) & \geq & \left(\frac{n}{13(Δ-1)^2}\right)^{\frac{\log_2(Δ-1)+1}{\log_2^2(Δ-1)+\log_2(Δ-1)+1}},\\[3mm] γ_e(G) & \leq & 2^{2{\rm r}-2}\mbox{, and }\\[3mm] γ_e(G) & \leq & \frac{43}{108}(n+2). \end{eqnarray*}

preprint2015arXiv

Doubled patterns are $3$ -avoidable

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.

preprint2015arXiv

Exponential Domination in Subcubic Graphs

As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if $S$ is a set of vertices of a graph $G$ , then $S$ is an exponential dominating set of $G$ if $\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}\geq 1$ for every vertex $u$ in $V(G)\setminus S$ , where ${\rm dist}_{(G,S)}(u,v)$ is the distance between $u\in V(G)\setminus S$ and $v\in S$ in the graph $G-(S\setminus \{ v\})$ . The exponential domination number $γ_e(G)$ of $G$ is the minimum order of an exponential dominating set of $G$ . In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If $G$ is a connected subcubic graph of order $n(G)$ , then $\frac{n(G)}{6\log_2(n(G)+2)+4}\leq γ_e(G)\leq \frac{1}{3}(n(G)+2).$ For every $ε>0$ , there is some $g$ such that $γ_e(G)\leq εn(G)$ for every cubic graph $G$ of girth at least $g$ . For every $0<α<\frac{2}{3\ln(2)}$ , there are infinitely many cubic graphs $G$ with $γ_e(G)\leq \frac{3n(G)}{\ln(n(G))^α}$ . If $T$ is a subcubic tree, then $γ_e(T)\geq \frac{1}{6}(n(T)+2).$ For a given subcubic tree, $γ_e(T)$ can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.

preprint2015arXiv

Islands in graphs on surfaces

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 that: (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.

preprint2015arXiv

The complexity of partitioning into disjoint cliques and a triangle-free graph

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.

preprint2014arXiv

Homomorphisms of signed planar graphs

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.

preprint2013arXiv

Application of entropy compression in pattern avoidance

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.

preprint2013arXiv

Near-colorings: non-colorable graphs and NP-completeness

A graph G is (d_1,..,d_l)-colorable if the vertex set of G can be partitioned into subsets V_1,..,V_l such that the graph G[V_i] induced by the vertices of V_i has maximum degree at most d_i for all 1 <= i <= l. In this paper, we focus on complexity aspects of such colorings when l=2,3. More precisely, we prove that, for any fixed integers k,j,g with (k,j) distinct form (0,0) and g >= 3, either every planar graph with girth at least g is (k,j)-colorable or it is NP-complete to determine whether a planar graph with girth at least g is (k,j)-colorable. Also, for any fixed integer k, it is NP-complete to determine whether a planar graph that is either (0,0,0)-colorable or non-(k,k,1)-colorable is (0,0,0)-colorable. Additionally, we exhibit non-(3,1)-colorable planar graphs with girth 5 and non-(2,0)-colorable planar graphs with girth 7.

preprint2012arXiv

Locally identifying coloring of graphs

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.

preprint2012arXiv

The Maximum Clique Problem in Multiple Interval Graphs

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$ .

Pascal Ochem

Research overview

Is this your work?

17 publications

Doubled patterns with reversal and square-free doubled patterns

Properties of a Ternary Infinite Word

Homomorphisms of planar $(m, n)$ -colored-mixed graphs to planar targets

Nice formulas, $xyx$ -formulas, and palindrome patterns

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

Avoidability of circular formulas

Avoidability of formulas with two variables

Bounds on the Exponential Domination Number

Doubled patterns are $3$ -avoidable

Exponential Domination in Subcubic Graphs

Islands in graphs on surfaces

The complexity of partitioning into disjoint cliques and a triangle-free graph

Homomorphisms of signed planar graphs

Application of entropy compression in pattern avoidance

Near-colorings: non-colorable graphs and NP-completeness

Locally identifying coloring of graphs

The Maximum Clique Problem in Multiple Interval Graphs

See the researcher in context

Building this map preview

Pascal Ochem

Research overview

Is this your work?

17 publications

Doubled patterns with reversal and square-free doubled patterns

Properties of a Ternary Infinite Word

Homomorphisms of planar (m,n)(m, n)(m,n)-colored-mixed graphs to planar targets

Nice formulas, xyxxyxxyx-formulas, and palindrome patterns

On non-repetitive sequences of arithmetic progressions:the cases k∈{4,5,6,7,8}k \in \{4,5,6,7,8\}k∈{4,5,6,7,8}

Avoidability of circular formulas

Avoidability of formulas with two variables

Bounds on the Exponential Domination Number

Doubled patterns are 333-avoidable

Exponential Domination in Subcubic Graphs

Islands in graphs on surfaces

The complexity of partitioning into disjoint cliques and a triangle-free graph

Homomorphisms of signed planar graphs

Application of entropy compression in pattern avoidance

Near-colorings: non-colorable graphs and NP-completeness

Locally identifying coloring of graphs

The Maximum Clique Problem in Multiple Interval Graphs

See the researcher in context

Building this map preview

Homomorphisms of planar $(m, n)$ -colored-mixed graphs to planar targets

Nice formulas, $xyx$ -formulas, and palindrome patterns

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

Doubled patterns are $3$ -avoidable