-
Metric dimension parameterized by treewidth in chordal graphs
Authors:
Nicolas Bousquet,
Quentin Deschamps,
Aline Parreau
Abstract:
The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A resolving set X of a graph G is a subset of vertices such that, for every pair (u,v) of vertices of G, there is a vertex x in X such that the distance between x and u and the distance between x and v are distinct. The metr…
▽ More
The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A resolving set X of a graph G is a subset of vertices such that, for every pair (u,v) of vertices of G, there is a vertex x in X such that the distance between x and u and the distance between x and v are distinct. The metric dimension of the graph is the minimum size of a resolving set. Computing the metric dimension of a graph is NP-hard even on split graphs and interval graphs.
Bonnet and Purohit proved that the metric dimension problem is W[1]-hard parameterized by treewidth. Li and Pilipczuk strenghtened this result by showing that it is NP-hard for graphs of treewidth. In this article, we prove that that metric dimension is FPT parameterized by treewidth in chordal graphs.
△ Less
Submitted 19 March, 2023;
originally announced March 2023.
-
Incidence, a Scoring Positional Game on Graphs
Authors:
Guillaume Bagan,
Quentin Deschamps,
Eric Duchêne,
Bastien Durain,
Brice Effantin,
Valentin Gledel,
Nacim Oijid,
Aline Parreau
Abstract:
Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first…
▽ More
Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity.
In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent.
We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.
△ Less
Submitted 2 November, 2022;
originally announced November 2022.
-
Partitioning into degenerate graphs in linear time
Authors:
Timothée Corsini,
Quentin Deschamps,
Carl Feghali,
Daniel Gonçalves,
Hélène Langlois,
Alexandre Talon
Abstract:
Let $G$ be a connected graph with maximum degree $Δ\geq 3$ distinct from $K_{Δ+ 1}$. Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if $p_1, \dots, p_s$ are non-negative integers such that $p_1 + \dots + p_s \geq Δ- s$, then $G$ admits a vertex partition into parts $A_1, \dots, A_s$ such that, for $1 \leq i \leq s$, $G[A_i]$ is $p_i$-degenerate. Here we show that such a part…
▽ More
Let $G$ be a connected graph with maximum degree $Δ\geq 3$ distinct from $K_{Δ+ 1}$. Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if $p_1, \dots, p_s$ are non-negative integers such that $p_1 + \dots + p_s \geq Δ- s$, then $G$ admits a vertex partition into parts $A_1, \dots, A_s$ such that, for $1 \leq i \leq s$, $G[A_i]$ is $p_i$-degenerate. Here we show that such a partition can be performed in linear time. This generalizes previous results that treated subcases of a conjecture of Abu-Khzam, Feghali and Heggernes~\cite{abu2020partitioning}, which our result settles in full.
△ Less
Submitted 22 March, 2023; v1 submitted 23 April, 2022;
originally announced April 2022.
-
Square coloring planar graphs with automatic discharging
Authors:
Nicolas Bousquet,
Lucas de Meyer,
Quentin Deschamps,
Théo Pierron
Abstract:
The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharg…
▽ More
The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress towards Wegner's conjecture for distance-$2$ coloring of planar graphs, by showing that $12$ colors are sufficient to color at distance $2$ every planar graph with maximum degree $4$.
△ Less
Submitted 12 April, 2022;
originally announced April 2022.
-
Strengthening a theorem of Meyniel
Authors:
Quentin Deschamps,
Carl Feghali,
František Kardoš,
Clément Legrand-Duchesne,
Théo Pierron
Abstract:
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $α$ and~$β$ whenever the coloring~$β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significan…
▽ More
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $α$ and~$β$ whenever the coloring~$β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$.
△ Less
Submitted 19 January, 2022;
originally announced January 2022.
-
Improved square coloring of planar graphs
Authors:
Nicolas Bousquet,
Quentin Deschamps,
Lucas de Meyer,
Théo Pierron
Abstract:
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac32Δ+1$ colors are sufficient to square color every planar graph of maximum degree $Δ$. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar…
▽ More
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac32Δ+1$ colors are sufficient to square color every planar graph of maximum degree $Δ$. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2Δ+7$ colors are sufficient, which improves the best known bounds when $6\leqslant Δ\leqslant 31$.
△ Less
Submitted 23 December, 2021;
originally announced December 2021.
-
Locating-dominating sets: from graphs to oriented graphs
Authors:
Nicolas Bousquet,
Quentin Deschamps,
Tuomo Lehtilä,
Aline Parreau
Abstract:
A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \notin S$, we have $N(u)\cap S\ne N(v)\cap S$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $w\in V$, $N[w]^-\cap S=\emptyset$ and for each pair of vertices…
▽ More
A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \notin S$, we have $N(u)\cap S\ne N(v)\cap S$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $w\in V$, $N[w]^-\cap S=\emptyset$ and for each pair of vertices $u,v\in V\setminus S$, $N^-(u)\cap S\ne N^-(v)\cap S$. We consider the following two parameters. Given an undirected graph $G$, we look for $\overset{\rightarrow}γ_{LD}(G)$ ($\overset{\rightarrow}Γ_{LD}(G))$ which is the size of the smallest (largest) optimal locating-dominating set over all orientations of $G$. In particular, if $D$ is an orientation of $G$, then $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(D)\leq\overset{\rightarrow}Γ_{LD}(G)$.
For the best orientation, we prove that, for every twin-free graph $G$ on $n$ vertices, $\overset{\rightarrow}γ_{LD}(G)\le n/2$ proving a ``directed version'' of a conjecture on $γ_{LD}(G)$. Moreover, we give some bounds for $\overset{\rightarrow}γ_{LD}(G)$ on many graph classes and drastically improve the value $n/2$ for (almost) $d$-regular graphs by showing that $\overset{\rightarrow}γ_{LD}(G)\in O(\log d/d\cdot n)$ using a probabilistic argument. While $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(G)$ holds for every graph $G$, we give some graph classes graphs for which $\overset{\rightarrow}Γ_{LD}(G)\geqγ_{LD}(G)$ and some for which $\overset{\rightarrow}Γ_{LD}(G)\leq γ_{LD}(G)$. We also give general bounds for $\overset{\rightarrow}Γ_{LD}(G)$. Finally, we show that for many graph classes $\overset{\rightarrow}Γ_{LD}(G)$ is polynomial on $n$ but we leave open the question whether there exist graphs with $\overset{\rightarrow}Γ_{LD}(G)\in O(\log n)$.
△ Less
Submitted 12 June, 2022; v1 submitted 3 December, 2021;
originally announced December 2021.
-
Metric dimension on sparse graphs and its applications to zero forcing sets
Authors:
Nicolas Bousquet,
Quentin Deschamps,
Aline Parreau,
Ignacio M. Pelayo
Abstract:
The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$. It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition…
▽ More
The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$. It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at most the metric dimension of $T$ plus $6c$. We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset $S$ of black vertices (whereas the other vertices are colored white) of $G$ such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph $G$, $dim(G)\leq Z(G) + c(G)$, where $c(G)$ is the number of edges that have to be removed from $G$ to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: $dim(G)\leq Z(G)+6c(G)$ holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.
△ Less
Submitted 2 June, 2022; v1 submitted 15 November, 2021;
originally announced November 2021.
