BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Pascal Ochem

Pascal Ochem appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsFormal Languages and Automata TheoryComputational Complexitymath.DS

Catalog footprint

What is connected

17works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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*}

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access