Source author record

Eric Sopena

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computer Science and Game Theory

Catalog footprint

Research overview

16works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

(α, β)-Modules in Graphs

Modular Decomposition focuses on repeatedly identifying a module M (a collection of vertices that shares exactly the same neighbourhood outside of M) and collapsing it into a single vertex. This notion of exactitude of neighbourhood is very strict, especially when dealing with real world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an (α, β)-module, a relaxation that allows a bounded number of errors in each node and maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal (α, β)-modules can be computed in polynomial time, and that every graph admits an (α,β)-modular decomposition tree, thus generalizing Gallai's Theorem (which corresponds to the case for α = β = 0). Unfortunately we give evidence that computing such a decomposition tree can be difficult.

preprint2021arXiv

On the Broadcast Independence Number of Circulant Graphs

An independent broadcast on a graph $G$ is a function $f: V \longrightarrow \{0,\ldots,{\rm diam}(G)\}$ such that $(i)$ $f(v)\leq e(v)$ for every vertex $v\in V(G)$ , where $\operatorname{diam}(G)$ denotes the diameter of $G$ and $e(v)$ the eccentricity of vertex $v$ , and $(ii)$ $d(u,v) > \max \{f(u), f(v)\}$ for every two distinct vertices $u$ and $v$ with $f(u)f(v)>0$ . The broadcast independence number $β_b(G)$ of $G$ is then the maximum value of $\sum_{v \in V} f(v)$ , taken over all independent broadcasts on $G$ . We prove that every circulant graph of the form $C(n;1,a)$ , $3\le a\le \lfloor\frac{n}{2} \rfloor$ , admits an optimal $2$ -bounded independent broadcast, that is, an independent broadcast~ $f$ satisfying $f(v)\le 2$ for every vertex $v$ , except when $n=2a+1$ , or $n=2a$ and $a$ is even. We then determine the broadcast independence number of various classes of such circulant graphs, and prove that, for most of these classes, the equality $β_b(C(n;1,a)) = α(C(n;1,a))$ holds, where $α(C(n;1,a))$ denotes the independence number of $C(n;1,a)$ .

preprint2020arXiv

A Connected Version of the Graph Coloring Game

The graph coloring game is a two-player game in which, given a graph G and a set of k colors, the two players, Alice and Bob, take turns coloring properly an uncolored vertex of G, Alice having the first move. Alice wins the game if and only if all the vertices of G are eventually colored. The game chromatic number of a graph G is then defined as the smallest integer k for which Alice has a winning strategy when playing the graph coloring game on G with k colors. In this paper, we introduce and study a new version of the graph coloring game by requiring that, after each player's turn, the subgraph induced by the set of colored vertices is connected. The connected game chromatic number of a graph G is then the smallest integer k for which Alice has a winning strategy when playing the connected graph coloring game on G with k colors. We prove that the connected game chromatic number of every outerplanar graph is at most 5 and that there exist outerplanar graphs with connected game chromatic number 4. Moreover, we prove that for every integer k $\ge$ 3, there exist bipartite graphs on which Bob wins the connected coloring game with k colors, while Alice wins the connected coloring game with two colors on every bipartite graph.

preprint2020arXiv

Broadcasts on Paths and Cycles

A broadcast on a graph $G=(V,E)$ is a function $f: V\longrightarrow \{0,\ldots,\operatorname{diam}(G)\}$ such that $f(v)\leq e\_G(v)$ for every vertex $v\in V$ , where $\operatorname{diam}(G)$ denotes the diameter of $G$ and $e\_G(v)$ the eccentricity of $v$ in $G$ . The cost of such a broadcast is then the value $\sum\_{v\in V}f(v)$ .Various types of broadcast functions on graphs have been considered in the literature, in relation with domination, irredundence, independenceor packing, leading to the introduction of several broadcast numbers on graphs.In this paper, we determine these broadcast numbers for all paths and cycles, thus answering a questionraised in [D.~Ahmadi, G.H.~Fricke, C.~Schroeder, S.T.~Hedetniemi and R.C.~Laskar, Broadcast irredundance in graphs. {\it Congr. Numer.} 224 (2015), 17--31].

preprint2020arXiv

Distinguishing numbers and distinguishing indices of oriented graphs

A distinguishing r-vertex-labelling (resp. r-edge-labelling) of an undirected graph G is a mapping $λ$ from the set of vertices (resp. the set of edges) of G to the set of labels {1,. .. , r} such that no non-trivial automorphism of G preserves all the vertex (resp. edge) labels. The distinguishing number D(G) and the distinguishing index D (G) of G are then the smallest r for which G admits a distinguishing r-vertex-labelling or r-edge-labelling, respectively. The distinguishing chromatic number D $χ$ (G) and the distinguishing chromatic index D $χ$ (G) are defined similarly, with the additional requirement that the corresponding labelling must be a proper colouring. These notions readily extend to oriented graphs, by considering arcs instead of edges. In this paper, we study the four corresponding parameters for oriented graphs whose underlying graph is a path, a cycle, a complete graph or a bipartite complete graph. In each case, we determine their minimum and maximum value, taken over all possible orientations of the corresponding underlying graph, except for the minimum values for unbalanced complete bipartite graphs K m,n with m = 2, 3 or 4 and n > 3, 6 or 13, respectively, or m $\ge$ 5 and n > 2 m -- m 2 , for which we only provide upper bounds.

preprint2020arXiv

Further Evidence Towards the Multiplicative 1-2-3 Conjecture

The product version of the 1-2-3 Conjecture, introduced by Skowronek-Kazi{ó}w in 2012, states that, a few obvious exceptions apart, all graphs can be 3-edge-labelled so that no two adjacent vertices get incident to the same product of labels. To date, this conjecture was mainly verified for complete graphs and 3-colourable graphs. As a strong support to the conjecture, it was also proved that all graphs admit such 4-labellings. In this work, we investigate how a recent proof of the multiset version of the 1-2-3 Conjecture by Vu{\v c}kovi{ć} can be adapted to prove results on the product version. We prove that 4-chromatic graphs verify the product version of the 1-2-3 Conjecture. We also prove that for all graphs we can design 3-labellings that almost have the desired property. This leads to a new problem, that we solve for some graph classes.

preprint2016arXiv

2-Distance Colorings of Integer Distance Graphs

A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors {1,. .. , k} such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number $χ$ 2 (G) of G is then the mallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = {d 1 ,. .. , d k }, the integer distance graph G = G(D) is the infinite graph defined by V (G) = Z and uv $\in$ E(G) if and only if |v -- u| $\in$ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with $χ$ 2 (G(D)) = Δ(G(D)) + 1.

preprint2016arXiv

Packing Coloring of Undirected and Oriented Generalized Theta Graphs

The packing chromatic number $χ$ $ρ$ (G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1,..., V k, in such a way that every two distinct vertices in V i are at distance (resp. directed distance) greater than i in G for every i, 1 $\le$ i $\le$ k. The generalized theta graph $Θ$ {\ell} 1,...,{\ell}p consists in two end-vertices joined by p $\ge$ 2 internally vertex-disjoint paths with respective lengths 1 $\le$ {\ell} 1 $\le$ . . . $\le$ {\ell} p. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n 3 + 2}, where n 3 = |{i / 1 $\le$ i $\le$ p, {\ell} i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k $\ge$ 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.

preprint2015arXiv

i-MARK: A New Subtraction Division Game

Given two finite sets of integers $S\subseteq\NNN\setminus\{0\}$ and $D\subseteq\NNN\setminus\{0,1\}$,the impartial combinatorial game $\IMARK(S,D)$ is played on a heap of tokens. From a heap of $n$ tokens, each player can moveeither to a heap of $n-s$ tokens for some $s\in S$ , or to a heap of $n/d$ tokensfor some $d\in D$ if $d$ divides $n$ .Such games can be considered as an integral variant of \MARK-type games, introduced by Elwyn Berlekamp and Joe Buhlerand studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of $n$ tokensto a heap of $\lfloor n/d\rfloor$ tokens for any $d\in D$ .Under normal convention, it is observed that the Sprague-Grundy sequence of the game $\IMARK(S,D)$ is aperiodic for any sets $S$ and $D$ .However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic.Moreover, in all these cases, the Sprague-Grundy value of a heap of $n$ tokens can be computed in time $O(\log n)$ .We also prove that, under misère convention, the outcome sequence of these games is purely periodic.

preprint2015arXiv

Ice sliding games

This paper deals with sliding games, which are a variant of the better known pushpush game. On a given structure (grid, torus...), a robot can move in a specific set of directions, and stops when it hits a block or boundary of the structure. The objective is to place the minimum number of blocks such that the robot can visit all the possible positions of the structure. In particular, we give the exact value of this number when playing on a rectangular grid and a torus. Other variants of this game are also considered, by constraining the robot to stop on each case, or by replacing blocks by walls.

preprint2015arXiv

Packing coloring of some undirected and oriented coronae graphs

The packing chromatic number $\pcn(G)$ of a graph $G$ is the smallest integer $k$ such that its set of vertices $V(G)$ can be partitioned into $k$ disjoint subsets $V\_1$ , \ldots, $V\_k$ , in such a way that every two distinct vertices in $V\_i$ are at distance greater than $i$ in $G$ for every $i$ , $1\le i\le k$ . For a given integer $p \ge 1$ , the generalized corona $G\odot pK\_1$ of a graph $G$ is the graph obtained from $G$ by adding $p$ degree-one neighbors to every vertex of $G$ . In this paper, we determine the packing chromatic number of generalized coronae of paths and cycles. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of generalized coronae of paths and cycles.

preprint2014arXiv

Outerplanar and planar oriented cliques

The clique number of an undirected graph $G$ is the maximum order of a complete subgraph of $G$ and is a well-known lower bound for the chromatic number of $G$ . Every proper $k$ -coloring of $G$ may be viewed as a homomorphism (an edge-preserving vertex mapping) of $G$ to the complete graph of order $k$ . By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this paper, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen [S. Sen. Maximum Order of a Planar Oclique Is 15. Proc. IWOCA'2012. {\em Lecture Notes Comput. Sci.} 7643:130--142]. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth $k$ for all $k \ge 4$ .

preprint2013arXiv

Incidence coloring game and arboricity of graphs

An incidence of a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge incident to $v$ . Two incidences $(v,e)$ and $(w,f)$ are adjacent whenever $v = w$ , or $e = f$ , or $vw = e$ or $f$ . The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980-1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number $i_g(G)$ of a graph $G$ is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on $G$ . Andres proved that % $\lceil 3/2 Δ(G)\rceil \le$ i_g(G) \le 2Δ(G) + 4k - 2 $for every$ k $-degenerate graph$ G $. %The arboricity$ a(G) $of a graph$ G $is the minimum number of forests into which its set of edges can be partitioned. %If$ G $is$ k $-degenerate, then$ a(G) \le k \le 2a(G) - 1 $. We show in this paper that$ i_g(G) \le \lfloor\frac{3Δ(G) - a(G)}{2}\rfloor + 8a(G) - 2 $for every graph$ G $, where$ a(G) $stands for the arboricity of$ G $, thus improving the bound given by Andres since$ a(G) \le k $for every$ k $-degenerate graph$ G $. Since there exists graphs with$ i_g(G) \ge \lceil\frac{3Δ(G)}{2}\rceil$, the multiplicative constant of our bound is best possible.

preprint2012arXiv

The Incidence Chromatic Number of Toroidal Grids

An incidence in a graph $G$ is a pair $(v,e)$ with $v \in V(G)$ and $e \in E(G)$ , such that $v$ and $e$ are incident. Two incidences $(v,e)$ and $(w,f)$ are adjacent if $v=w$ , or $e=f$ , or the edge $vw$ equals $e$ or $f$ . The incidence chromatic number of $G$ is the smallest $k$ for which there exists a mapping from the set of incidences of $G$ to a set of $k$ colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid $T_{m,n}=C_m\Box C_n$ equals 5 when $m,n \equiv 0 \pmod 5$ and 6 otherwise.

preprint2010arXiv

Coloring the square of the Cartesian product of two cycles

The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ in such a way that distinct vertices with distance at most two in $G$ are joined by an edge. We study the chromatic number of the square of the Cartesian product $C_m\Box C_n$ of two cycles and show that the value of this parameter is at most 7 except when $m=n=3$ , in which case the value is 9, and when $m=n=4$ or $m=3$ and $n=5$ , in which case the value is 8. Moreover, we conjecture that whenever $G=C_m\Box C_n$ , the chromatic number of $G^2$ equals $\lceil mn/α(G^2) \rceil$ , where $α(G^2)$ denotes the size of a maximal independent set in $G^2$ .

preprint2010arXiv

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

The oriented chromatic number of an oriented graph $\vec G$ is the minimum order of an oriented graph $\vev H$ such that $\vec G$ admits a homomorphism to $\vev H$. The oriented chromatic number of an undirected graph $G$ is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph $G$ , defined as the minimum order of an oriented graph $\vev U$ such that every orientation $\vec G$ of $G$ admits a homomorphism to $\vec U$ . We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of Cartesian, strong, direct and lexicographic products of graphs, and consider the particular case of products of paths.

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.

Eric Sopena

Research overview

Is this your work?

16 publications

(α, β)-Modules in Graphs

On the Broadcast Independence Number of Circulant Graphs

A Connected Version of the Graph Coloring Game

Broadcasts on Paths and Cycles

Distinguishing numbers and distinguishing indices of oriented graphs

Further Evidence Towards the Multiplicative 1-2-3 Conjecture

2-Distance Colorings of Integer Distance Graphs

Packing Coloring of Undirected and Oriented Generalized Theta Graphs

i-MARK: A New Subtraction Division Game

Ice sliding games

Packing coloring of some undirected and oriented coronae graphs

Outerplanar and planar oriented cliques

Incidence coloring game and arboricity of graphs

The Incidence Chromatic Number of Toroidal Grids

Coloring the square of the Cartesian product of two cycles

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

See the researcher in context

Building this map preview