A proper k -colouring of a graph G = (V, E) is a function c : V(G) → {1,..., k} such that c(u) ≠ c(v) for every edge uv ∈ E(G). The chromatic number χ(G) is the minimum k such that there exists a proper k -colouring of G. Given a spanning subgraph H of G , a q-backbone k -colouring of (G,H) is a proper k -colouring c of G such that | c(u) - c(v) | ≥ q for every edge uv ∈ E(H). The q -backbone chromatic number BBC q (G, H) is the smallest k for which there exists a q -backbone k-colouring of (G,H). In their seminal paper, Broersma et al. [12] ask whether, for any chordal graph G and any spanning forest H of G , we have that BBC 2 ( G, H) ≤ χ( G ) + O( 1) . In this work, we first show that this is true as long as H is bipartite and G is an interval graph in which each vertex belongs to at most two maximal cliques. We then show that this does not extend to bipartite graphs as backbone by exhibiting a family of chordal graphs G with spanning bipartite subgraphs H satisfying BBC 2 (G,H)≥5χ(G)/3. Then, we show that if G is chordal and H has bounded maximum average degree (in particular, if H is a forest), then BBC 2 (G,H)≤χ(G) + O(√χ(G)). We finally show that BBC 2 (G,H) ≤ 3/2χ(G) + O(1) holds whenever G is chordal and H is C 4 -free.

The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ϵ N , Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • •, k] such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob wins otherwise. The game chromatic number χ g (G) is the smallest integer k such that Alice has a winning strategy with k colors in G . It has been recently (2020) shown that, given a graph G and k ϵ N, deciding whether χ g (G) ≤ k is PSPACE-complete. Surprisingly, this parameter is not well understood even in “simple” graph classes. Let P n denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χ g ( P m □ P n ) ≤ 5 since χ g (G) ≤ ∆ + 1 for any graph G with maximum degree ∆. However, the exact value is only known for small values of m , namely χ g (P 1 □ P n ) = 3, χ g (P 2 □ P n ) = 4 and χ g ( P 3 □ Pn ) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χ g ( P 4 □ P n ) = 4.

An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G, denoted by →χ (G), is the minimum k such that G has a proper k-orientation. A weighted orientation of a graph G is a pair (D, w), where D is an orientation of G and w is an arc-weighting A(D) → N \ {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such that for every two adjacent vertices u and v in G, we have that S(d,w)(v) ≠ S(d,w)(u), where S(d,w)(v) is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper k-orientation (D, w) of a graph G is a semi-proper orientation of G such that maxvϵV(G) S(d,w)(v) ≤ k. The semi-proper orientation number of a graph G, denoted by →χs(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that →χs(G) ϵ {ω(G) - 1, ω(G)} for every split graph G, and that, given a split graph G, deciding whether →χs(G) = ω(G) - 1 is an NP-complete problem. We also show that, for every k, there exists a (chordal) graph G and a split subgraph H of G such that →χ(G) ≤ k and →χ(H) = 2k - 2. In the sequel, we show that, for every n ≥ p(p + 1), →χs(Ppn) = [3/2 p], where Ppn is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that →χ(G) ≤ 3 for any unit interval graph G with ω(G) = 3, and present a complete characterization of unit interval graphs with →χ(G)= ω(G) = 3. Then, we show that deciding whether →χs(G) = ω(G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing →χs(G) is FPT when parameterized by the minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing →χs(G) but also →χ(G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 40(k2) and 0(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether →χs(G) ≤ k parameterized by k. We also present exponential kernels for computing both →χ(G) and →χs(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing →χs(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP ⊆ coNP/poly.

In the field of complex networks, hypergraph models have so far received significantly less attention than graphs. However, many real-life networks feature multiary relations (co-authorship, protein reactions) may therefore be modeled way better by hypergraphs. Also, a recent study by Broido and Clauset suggests that a power-law degree distribution is not as ubiquitous in the natural systems as it was thought so far. They experimentally confirm that a majority of networks (56% of around 1000 networks that undergone the test) favor a power-law with an exponential cutoff over other distributions. We address the two above observations by introducing a preferential attachment hypergraph model which allows for vertex deactivations. The phenomenon of vertex deactivations is rare in existing theoretical models and omnipresent in real-life scenarios (social network accounts which are not maintained forever, collaboration networks in which people retire, technological networks in which devices break down). We prove that the degree distribution of the proposed model follows a power-law with an exponential cutoff. We also check experimentally that a Scopus collaboration network has the same characteristic. We believe that our model will predict well the behavior of systems from a variety of domains.

The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing h(G) remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G)+1 for any graph G with pathwidth pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant, is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e., that monotonicity does not help. In particular, we show that, for every k ≥ 3, there exists a tree T with h(T) = 2 and mh(T) = k. We conclude by proving that computing h (resp., mh) is FPT parameterised by the minimum size of a vertex cover.

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar graphs, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of infinite families of forbidden isometric subgraphs.

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $$\gamma ^{\infty }_{all}$$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $$P_n\boxtimes P_m$$ . Cartesian grids $$P_n \square P_m$$ have been vastly studied with tight bounds existing for small grids such as $$k\times n$$ grids for $$k\in \{2,3,4,5\}$$ . It was recently proven that $$\gamma ^{\infty }_{all}(P_n \square P_m)=\gamma (P_n \square P_m)+O(n+m)$$ where $$\gamma (P_n \square P_m)$$ is the domination number of $$P_n \square P_m$$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27–46, 2019]. We prove that, for all $$n,m\in \mathbb {N^*}$$ such that $$m\ge n$$ , $$\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor +\Omega (n+m)=\gamma _{all}^{\infty } (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$$ (note that $$\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$$ is the domination number of $$P_n\boxtimes P_m$$ ). We then generalise our technique to prove that $$\gamma _{all}^{\infty }(G)=\gamma (G)+o(\gamma (G))$$ for all graphs $$G\in {\mathcal {F}}$$ , where $${\mathcal {F}}$$ is a large family of D-dimensional grids which are supergraphs of the D-dimensional Cartesian grid and subgraphs of the D-dimensional strong grid. In particular, $${\mathcal {F}}$$ includes both the D-dimensional Cartesian grid and the D-dimensional strong grid.

The 1–2–3 Conjecture asserts that, for every connected graph different from K2, its edges can be labeled with 1,2,3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1–2–3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP-complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permit to reduce the maximum color.

The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a vertex s to a vertex t in a digraph. Yen (1971) proposed the first algorithm with the best known theoretical complexity of O(kn(m+n log n)) for a digraph with n vertices and m arcs. Since then, the problem has been widely studied from an algorithm engineering perspective, and impressive improvements have been achieved. In particular, Kurz and Mutzel (2016) proposed a sidetracks-based (SB) algorithm which is currently the fastest solution. In this work, we propose two improvements of this algorithm. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees. We did experiments on some road networks of the 9th DIMAC'S challenge with up to about half a million nodes and one million arcs. Our computational results show an average speed up by a factor of 1.5 to 2 with a similar working memory consumption as SB. We then propose a second algorithm enabling to significantly reduce the working memory at the cost of an increase of the running time (up to two times slower). Our experiments on the same data set show, on average, a reduction by a factor of 1.5 to 2 of the working memory.

In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.

Tree-likeness parameters have proven their utility in the design of efficient algorithms on graphs. In this paper, we relate the structural tree-likeness of graphs with their metric tree-likeness. To this end, we establish new upper bounds on the diameter of minimal separators in graphs. We prove that in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor \ell(G) / 2\rfloor \cdot (|S|-1)$, with $\ell(G)$ the length of a longest isometric cycle in $G$. Our result relies on algebraic methods and on the cycle basis of graphs. We improve our bound for the graphs admitting a distance preserving elimination ordering, for which we prove that any minimal separator $S$ has diameter at most $2 \cdot (|S|-1)$. We use our results to prove that the treelength $tl(G)$ of any graph $G$ is at most $\lfloor \ell(G) / {2}\rfloor$ times its treewidth $tw(G)$. In addition, we prove that, for any graph $G$ that excludes an apex graph $H$ as a minor, $tw(G) \leq c_H \cdot tl(G)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. Altogether, we obtain a simple $\mathcal{O} (\ell(G))$-approximation algorithm for computing the treewidth of $n$-node apex-minor-free graphs in $\mathcal{O}(n^2)$-time.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph $G$ as the smallest weight of a proper coloring of $G$. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. the max coloring problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes; in particular, there exists a polynomial-time approximation scheme for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The exponential time hypothesis (ETH) states that 3-SAT cannot be solved in subexponential time. We show that, assuming the ETH, the best algorithm to compute the weighted chromatic number of $n$-node trees has time-complexity $n^{\Theta(\log n)}$. Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph $G$, it is hard to combine colorings of its connected components.

In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a non-linear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NP-complete for a 2-nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem can be solved in polynomial time. We design heuristics for this problem and analyze their behavior through simulations.

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that {\it separate} these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes-which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3?" cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded tree width graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.

In the classical cop and robber game, two players, the cop $\mathcal{C}$ and the robber $\mathcal{R}$, move alternatively along edges of a finite graph $G=(V,E)$. The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski and Winkler [Discrete Math., 43 (1983), pp. 235–239] and Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'état, Université de Paris VI, Paris, 1983] characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class $\mathcal{CWFR}(s,s')$ of cop-win graphs in the game in which the robber and the cop move at different speeds s and $s'$, $s'\leq s$. We also establish some connections between cop-win graphs for this game with $s'1$. In particular, we characterize the graphs which are cop-win for any value of k.

We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2Ω(min d,k}), for any d,k = O(log n), even when G is a tree.