Author: "Frédéric Havet" / Topic: [info.info-dm]computer science [cs]/discrete mathematics [cs.dm] - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Frédéric Havet"' showing total 57 results

Start Over Author "Frédéric Havet" Topic [info.info-dm]computer science [cs]/discrete mathematics [cs.dm]

57 results on '"Frédéric Havet"'

1. Constrained ear decompositions in graphs and digraphs

Author: Frédéric Havet and Nicolas Nisse
Subjects: [info.info-dm]computer science [cs]/discrete mathematics [cs.dm], [info.info-cc]computer science [cs]/computational complexity [cs.cc], Mathematics, QA1-939
Abstract: Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 −)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is N P-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is N P-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is N P-complete, unless there exists h ∈ N such that A = {1, · · · , h}.
Published: 2019
Full Text: View/download PDF

2. Backbone colouring and algorithms for TDMA scheduling

Author: Julien Bensmail, Thibaut Blanc, Nathann Cohen, Frédéric Havet, and Leonardo Rocha
Subjects: wireless networks, tdma scheduling, backbone colouring, algorithmic complexity, [info.info-dm]computer science [cs]/discrete mathematics [cs.dm], Mathematics, QA1-939
Abstract: We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.
Published: 2019
Full Text: View/download PDF

3. On the Nash number and the diminishing Grundy number of a graph

Author: Frédéric Havet, Allen Ibiapina, Leonardo Rocha, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Federal do Ceará = Federal University of Ceará (UFC), and State University of Ceara / Universidade Estadual do Ceara (UECE)
Subjects: Applied Mathematics, Grundy colouring, Discrete Mathematics and Combinatorics, Complexity, Colouring parameters, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Colouring, Game theory
Abstract: International audience; A Nash k-colouring is a k-colouring (S1, . . . , Sk) such that every vertex of Si is adjacent to a vertex in Sj, whenever |Sj| ≥ |Si|. The Nash Number of G, denoted by Nn(G), is the largest k such that G admits a Nash k-colouring. A diminishing greedy k-colouring is a k-colouring (S1, . . . , Sk) such that, for all 1 ≤ j < i ≤ k, |Si| ≤ |Sj| and every vertex of Si is adjacent to a vertex in Sj. The diminishing Grundy Number of G, denoted by Γ ↓(G), is the largest k such that G admits a diminishing greedy k-colouring. In this paper, we prove some properties of Nn and Γ ↓. We mainly study the relations between them and other graph parameters such as the clique number ω, the chromatic number χ , the Grundy number Γ , and the maximum degree ∆. In particular we study the chain of inequalities ω(G) ≤ χ(G) ≤ Nn(G) ≤ Γ ↓(G) ≤ Γ (G) ≤ ∆(G)+1. We show each inequality γ1(G) ≤ γ2(G) of this chain is loose, in the sense that there is no function f such that γ2(G) ≤ f (γ1(G)). We also prove the existence or non-existence of inequalities analogue to Reed’s one stating that there exists ε > 0 such that χ (G) ≤ εω(G) + (1 − ε)(∆(G) + 1).We then study the Nash number and the diminishing Grundy number of trees and forests, and prove that Γ (F ) − 1 ≤ Nn(F ) ≤ Γ ↓(F ) ≤ Γ (F ).Finally we study the complexity of related problems. We show that computing the Nash number or the diminishing Grundy number is NP-hard even when the input graph is bipartite or chordal. We also show that deciding whether a graph satisfies γ1(G) = γ2(G) is NP-hard for every pair (γ1, γ2) with γ1 ∈ {Nn, Γ ↓} and γ2 ∈ {ω, χ , Γ , ∆ + 1}
Published: 2022
Full Text: View/download PDF

4. On the dichromatic number of surfaces

Author: Frédéric Havet, Clément Rambaud, Kolja Knauer, Pierre Aboulker, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: dichromatic number, 010102 general mathematics, Torus, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Surface (topology), graphs on surfaces, 01 natural sciences, planar graphs, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Euler characteristic, symbols, Projective plane, 0101 mathematics, Klein bottle, Mathematics
Abstract: In this paper, we give bounds on the dichromatic number $\overrightarrow{\chi }(\varSigma )$ of a surface $\varSigma $, which is the maximum dichromatic number of an oriented graph embeddable on $\varSigma $. We determine the asymptotic behaviour of $\overrightarrow{\chi }(\varSigma )$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log (-c)} \le \overrightarrow{\chi }(\varSigma ) \le a_2 \frac{\sqrt{-c}}{\log (-c)} $ for every surface $\varSigma $ with Euler characteristic $c\le -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $\mathbb {N}_1$, the Klein bottle $\mathbb {N}_2$, the torus $\mathbb {S}_1$, and Dyck’s surface $\mathbb {N}_3$ are all equal to 3, and that the dichromatic numbers of the 5-torus $\mathbb {S}_5$ and the 10-cross surface $\mathbb {N}_{10}$ are equal to 4.
Published: 2021
Full Text: View/download PDF

5. On the semi-proper orientations of graphs

Author: Ali Dehghan, Frédéric Havet, Carleton University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Degeneracy (graph theory), Graph, Vertex (geometry), Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Outerplanar graph, Bipartite graph, symbols, Discrete Mathematics and Combinatorics, Mathematics
Abstract: International audience; 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 of D, that is an application A(D) → N \ {0}. The in-weight of a vertex v in a weighted orientation (D, w), denoted by S (D,w) (v), is the sum of the weights of arcs with head v in D. A semi-proper orientation is a weighted orientation such that two adjacent vertices have different in-weights. The semiproper orientation number of a graph G, denoted by − → χs(G), is min (D,w)∈Γ max v∈V (G) S (D,w) (v), where Γ is the set of all semi-proper orientations of G. A semi-proper orientation (D, w) of a graph G is optimal if max v∈V (G) S (D,w) (v) = − → χs(G). In this work, we show that every graph G has an optimal semi-proper orientation (D, w) such that the weight of each arc is 1 or 2. We then give some bounds on the semi-proper orientation number: we show Mad(G) 2 ≤ − → χs(G) ≤ Mad(G) 2 +χ(G)−1 and δ * (G)+1 2 ≤ − → χs(G) ≤ 2δ * (G) for all graph G, where Mad(G) and δ * (G) are the maximum average degree and the degeneracy of G, respectively. We then deduce that the maximum semi-proper orientation number of a tree is 2, of a cactus is 3, of an outerplanar graph is 4, and of a planar graph is 6. Finally, we consider the computational complexity of associated problems: we show that determining whether − → χs(G) = χ(G) is NP-complete for planar graphs G with − → χs(G) = 2; we also show that deciding whether − → χs(G) ≤ 2 is NP-complete for planar bipartite graphs G.
Published: 2021
Full Text: View/download PDF

6. A variant of the Erdős‐Sós conjecture

Author: Maya Stein, David R. Wood, Bruce Reed, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), Monash University [Melbourne], Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Conjecture, Degree (graph theory), 010102 general mathematics, Graph theory, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Mathematics
Abstract: International audience; A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m−1$ contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.
Published: 2020
Full Text: View/download PDF

7. Minimum density of identifying codes of king grids

Author: Rennan Dantas, Frédéric Havet, Rudini Menezes Sampaio, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Applied Mathematics, Discharging method, Neighbourhood (graph theory), identifying codes, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, king grids, Discharging Method, 010201 computation theory & mathematics, Identifying code, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, King grid, Minimum density, Mathematics
Abstract: A set C ⊆ V ( G ) is an identifying code in a graph G if for all v ∈ V ( G ) , C [ v ] ≠ ∅ , and for all distinct u , v ∈ V ( G ) , C [ u ] ≠ C [ v ] , where C [ v ] = N [ v ] ∩ C and N [ v ] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d ⁎ ( G ) . In this paper, we study the density of king grids which are strong product of two paths. We show that for every king grid G , d ⁎ ( G ) ≥ 2 / 9 . In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given k ≥ 3 , we denote by K k the (infinite) king strip with k rows. We prove that d ⁎ ( K 3 ) = 1 / 3 , d ⁎ ( K 4 ) = 5 / 16 , d ⁎ ( K 5 ) = 4 / 15 and d ⁎ ( K 6 ) = 5 / 18 . We also prove that 2 9 + 8 81 k ≤ d ⁎ ( K k ) ≤ 2 9 + 4 9 k for every k ≥ 7 .
Published: 2017
Full Text: View/download PDF

8. Cooperative colorings of trees and of bipartite graphs

Author: Frédéric Havet, Eli Berger, Zilin Jiang, Ron Aharoni, Maria Chudnovsky, Department of Mathematics (TECHNION), Technion - Israel Institute of Technology [Haifa], University of Haifa [Haifa], Columbia University [New York], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Massachusetts Institute of Technology (MIT), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Vertex (graph theory), 05C15, 05C69, Mathematics::Commutative Algebra, Applied Mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Computer Science::Discrete Mathematics, Bipartite graph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Geometry and Topology, Combinatorics (math.CO), Mathematics
Abstract: Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$, a cooperative coloring is a choice of vertex sets $I_1, \ldots ,I_m$, such that $I_j$ is independent in $G_j$ and $\bigcup_{j=1}^{m}I_j = V$. For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $\Omega(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $\Omega(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$, where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs., Comment: 8 pages, 2 figures, accepted to the Electronic Journal of Combinatorics, corrections suggested by the referees have been incorporated
Published: 2020

9. Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

Author: Joergen Bang-Jensen, Anders Yeo, Matthias Kriesell, Frédéric Havet, University of Southern Denmark (SDU), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Technische Universität Ilmenau (TU ), University of Johannesburg [South Africa] (UJ), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015)
Subjects: strong connectivity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], semicomplete digraph, 05C20, 05C15, edge-disjoint spanning trees, Combinatorics, Integer, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, arc-connectivity, majority colouring, ComputingMilieux_MISCELLANEOUS, Mathematics, Spanning tree, Conjecture, Mathematics::Combinatorics, Degree (graph theory), Digraph, Directed graph, Vertex (geometry), bipartite graph, Bipartite graph, Geometry and Topology, Combinatorics (math.CO), edge-connectivity
Abstract: Generalizing well-known results of Erdős and Lovász, we show that every graph (Formula presented.) contains a spanning (Formula presented.) -partite subgraph (Formula presented.) with (Formula presented.), where (Formula presented.) is the edge-connectivity of (Formula presented.). In particular, together with a well-known result due to Nash-Williams and Tutte, this implies that every 7-edge-connected graph contains a spanning bipartite graph whose edge set decomposes into two edge-disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6-edge-connected graphs. For directed graphs, it was shown by Bang-Jensen et al. that there is no (Formula presented.) such that every (Formula presented.) -arc-connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3-partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer (Formula presented.), every (Formula presented.) -arc-connected digraph contains a spanning ((Formula presented.))-partite subdigraph which is (Formula presented.) -arc-connected and this is best possible. A conjecture by Kreutzer et al. implies that every digraph of minimum out-degree (Formula presented.) contains a spanning 3-partite subdigraph with minimum out-degree at least (Formula presented.). We prove that the bound (Formula presented.) would be best possible by providing an infinite class of digraphs with minimum out-degree (Formula presented.) which do not contain any spanning 3-partite subdigraph in which all out-degrees are at least (Formula presented.). We also prove that every digraph of minimum semidegree at least (Formula presented.) contains a spanning 6-partite subdigraph in which every vertex has in- and out-degree at least (Formula presented.).
Published: 2020
Full Text: View/download PDF

10. Powers of paths in tournaments

Author: Alex Scott, Benny Sudakov, Jacob Fox, Frédéric Havet, Nemanja Draganić, Dániel Korándi, François Dross, António Girão, David Munhá Correia, William Lochet, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Stanford University, Heidelberg University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Oxford [Oxford], University of Bergen (UiB), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and University of Oxford
Subjects: Statistics and Probability, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Square (algebra), Theoretical Computer Science, Power (physics), Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Path (graph theory), FOS: Mathematics, Mathematics - Combinatorics, Tournament, Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract: In this short note we prove that every tournament contains the $k$-th power of a directed path of linear length. This improves upon recent results of Yuster and of Gir\~ao. We also give a complete solution for this problem when $k=2$, showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$, which is best possible., Comment: 6 pages; updated affiliations; accepted at CPC
Published: 2020
Full Text: View/download PDF

11. On the Unavoidability of Oriented Trees

Author: François Dross, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (1965 - 2019) (UNS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Arborescence, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Unavoidable, Tree (descriptive set theory), oriented trees, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Order (group theory), Tournament, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Oriented tree, 010102 general mathematics, Ramsey theory, 020207 software engineering, Digraph, unavoidability, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science - Discrete Mathematics
Abstract: A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is ( n + k − 1 ) -unavoidable. We then prove that every oriented tree of order n ( n ≥ 2 ) with k leaves is ( 3 2 n + 3 2 k − 2 ) -unavoidable and ( 9 2 n − 5 2 k − 9 2 ) -unavoidable, and thus ( 21 8 n − 47 16 ) -unavoidable. Finally, we prove that every oriented tree of order n with k leaves is ( n + 144 k 2 − 280 k + 124 ) -unavoidable.
Published: 2019
Full Text: View/download PDF

12. Proper orientation of cacti

Author: Júlio Araújo, Cláudia Linhares Sales, Ana Silva, Frédéric Havet, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Factor-critical graph, General Computer Science, planar graph, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], cactus graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Graph power, Outerplanar graph, graph coloring, 0202 electrical engineering, electronic engineering, information engineering, Graph minor, Complement graph, Mathematics, Discrete mathematics, block graph, Cactus graph, 020206 networking & telecommunications, Butterfly graph, claw-free graph, 010201 computation theory & mathematics, proper orientation, Null graph
Abstract: International audience; An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number − → χ (G) of a graph G is the minimum maximum in-degree of a proper orientation of G. In [1], the authors ask whether the proper orientation number of a planar graph is bounded. We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.
Published: 2016
Full Text: View/download PDF

13. Overlaying a hypergraph with a graph with bounded maximum degree

Author: Dorian Mazauric, Frédéric Havet, Viet-Ha Nguyen, Rémi Watrigant, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Computational complexity theory, 0102 computer and information sciences, Overlay, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], complexité, biologie structurale computationnelle, 01 natural sciences, Combinatorics, biologie structurale computation-nelle, 03 medical and health sciences, graphes, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], 030304 developmental biology, Mathematics, 0303 health sciences, algorithm, Applied Mathematics, hypergraphes, graph, Graph, graphe, 010201 computation theory & mathematics, Bounded function, complexity, Hypergraphe, algorithme, algorithmes, computational structural biology
Abstract: International audience; Let G be a graph and H a hypergraph with the same set of vertices and let F be a fixed graph. The graph GF overlays a hyperedge S of H if F is a covering subgraph of the subgraph of G induced by S. The graph GF-overlaying H if F overlays each hyperedge of H. We have analyze the complexity of the following two problems. The first problem, ($∆ ≤ k$) F-OVERLAY, consists in deciding if there is a graph of maximum degree at most k which F overlays a given hypergraph H. This is a special case of the second problem, MAX ($∆ ≤ k$) F-OVERLAY, which, given a hypergraph H and an integer s, consists in deciding whether there is a graph of maximum degree at most k which F overlays at least s hyper edges of H. We prove a polynomial /NP-complete dichotomy for the MAX ($∆ ≤ k$) -F-OVERLAY, and prove the complexity of the problem ($∆ ≤ k$) F-OVERLAY for a large number of pairs (F, k). These two problems model a central problem in computational structural biology: the determination of the contacts between the proteins of a macromolecular assembly. The vertices are the proteins, the hyperedges are the known complexes, the graph F is the generic graph whose edges correspond to the contacts between the proteins of the assembly. Determining the graph G then comes down to finding the contacts between the proteins so that the graph F is a subgraph covering in each hyperedge and so that the degree is bounded (a protein is in contact with a limited number of others proteins). Finally, these problems are of more general interest for network inference problems.; Soient G un graphe et H un hypergraphe avec le même ensemble de sommets et soit F un graphe fixé. Le graphe GF-revouvre une hyperarête S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S. Le graphe GF-revouvre H s’il F-revouvrechaque hyperarête de H. Nous avons analysé la complexité des deux problèmes suivants. Le premier problème, ($∆ ≤ k$) F-OVERLAY, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre un hypergraphe H donné. C'est un cas particulier du second problème, MAX ($∆ ≤ k$) F-OVERLAY, qui,étant donné un hypergraphe H et un entier s, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre au moins s hyperarêtes de H. Nous prouvons une dichotomie polynomial/N P-complet pour le problème MAX ($∆ ≤ k$)-F-OVERLAY dépendant de la paire (F, k), et prouvons la complexité du problème ($∆ ≤ k$) F-OVERLAY pour un grand nombre de paires (F, k). Ces deux problèmes modélisent un problème central en biologie structurale computationnelle : la détermination des contacts entre les protéines d'un assemblage macromoléculaire. Les sommets sont les protéines, les hyperarêtes sont les complexes connus, le graphe F est le graphe générique dont les arêtes correspondent aux contacts entre les protéines de l'assemblage. Déterminer le graphe G revient alorsà trouver les contacts entre les protéines de telle sorte que le graphe F soit un sous-graphe couvrant dans chaque hyperarête et de telle sorte que le degré soit borné (une protéine est en contact avec un nombre limité d'autres protéines). Enfin, ces problèmes sont d'intérêt plus général pour les problèmes d'inférence de réseaux.
Published: 2019
Full Text: View/download PDF

14. Subdivisions in digraphs of large out-degree or large dichromatic number

Author: Frédéric Havet, Nathann Cohen, Phablo F. S. Moura, William Lochet, Pierre Aboulker, Stéphan Thomassé, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universidade Estadual de Campinas (UNICAMP), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Paris (ENS-PSL), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Estadual de Campinas = University of Campinas (UNICAMP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Tournament, [INFO]Computer Science [cs], [MATH]Mathematics [math], Subdivision, Mathematics, Transitive relation, Conjecture, Mathematics::Combinatorics, business.industry, Applied Mathematics, Out degree, Digraph, Graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract: In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$ is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from $x$ to $y$ and a directed path from $y$ to $x$, then every digraph with minimum out-degree large enough contains a subdivision of $D$. Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision.
Published: 2019

15. $χ$-bounded families of oriented graphs

Author: Pierre Charbit, Frédéric Maffray, Nicolas Bousquet, Frédéric Havet, José Zamora, Jørgen Bang-Jensen, Pierre Aboulker, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Southern Denmark (SDU), OC (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Universidad Andrés Bello - UNAB (CHILE), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Department of Mathematics and Computer Science [Odense] (IMADA), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universidad Andrés Bello [Santiago] (UNAB), ANR-13-BS02-0007,Stint,Structures Interdites(2013), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), This work was supported by ANR under contract STINT ANR-13-BS02-0007., COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Université Côte d'Azur (UCA), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)
Subjects: Transitive relation, Conjecture, Mathematics::Combinatorics, 010102 general mathematics, Induced subgraph, Digraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, clique number, Combinatorics, 010201 computation theory & mathematics, chromatic number, Computer Science::Discrete Mathematics, Bounded function, χ-bounded, Discrete Mathematics and Combinatorics, Tournament, Geometry and Topology, Chromatic scale, 0101 mathematics, Mathematics, Computer Science - Discrete Mathematics
Abstract: A famous conjecture of Gy\'arf\'as and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results., Comment: 27 pages, 4 figures
Published: 2018
Full Text: View/download PDF

16. Complexity dichotomies for the Minimum F -Overlay problem

Author: Frédéric Havet, Dorian Mazauric, Ignasi Sau, Nathann Cohen, Rémi Watrigant, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Algorithms, Biology, Structure (ABS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidade Federal do Ceará = Federal University of Ceará (UFC), Projet de Recherche Exploratoire Inria: Improving inference algorithms for macromolecular structure determination, ANR-13-BS02-0007,Stint,Structures Interdites(2013), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), This work was partially funded by ‘Projet de Recherche Exploratoire’, Inria, Improving inference algorithms for macromolecular structure determination, Inria Sophia Antipolis, CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Dichotomy, Subgraph isomorphism problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Overlay, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Induced subgraph isomorphism problem, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Complete graph, 020206 networking & telecommunications, NP-completeness, Minimum F-Overlay Problem, Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, Fixed-parameter tractability
Abstract: International audience; For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V (H) is equal to V (G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph. While it is easy to see that the complete graph on |V (H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks. Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edge-less graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete. We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution. This yields an FPT/W[1]-hard dichotomy for a relaxed problem , where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.
Published: 2018
Full Text: View/download PDF

17. Bispindles in strongly connected digraphs with large chromatic number

Author: Raul Lopes, Nathann Cohen, Frédéric Havet, William Lochet, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Laboratoire de Recherche en Informatique ( LRI ), Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ), Combinatorics, Optimization and Algorithms for Telecommunications ( COATI ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -COMmunications, Réseaux, systèmes Embarqués et Distribués ( COMRED ), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S ), Université Nice Sophia Antipolis ( UNS ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Nice Sophia Antipolis ( UNS ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ), Parallelism, Graphs and Optimization Research Group ( ParGO ), Universidade Federal do Ceará ( UFC ), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Discrete mathematics, Strongly connected component, Conjecture, Applied Mathematics, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Integer, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Geometry and Topology, Chromatic scale, Combinatorics (math.CO), Mathematics
Abstract: A $(k_1+k_2)$-bispindle is the union of $k_1$ $(x,y)$-dipaths and $k_2$ $(y,x)$-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every $(1,1)$- bispindle $B$, there exists an integer $k$ such that every strongly connected digraph with chromatic number greater than $k$ contains a subdivision of $B$. We investigate generalizations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any $(3,0)$-bispindle or $(2,2)$-bispindle. We then consider $(2,1)$-bispindles. Let $B(k_1,k_2;k_3)$ denote the $(2,1)$-bispindle formed by three internally disjoint dipaths between two vertices $x,y$, two $(x,y)$-dipaths, one of length $k_1$ and the other of length $k_2$, and one $(y,x)$-dipath of length $k_3$. We conjecture that for any positive integers $k_1, k_2,k_3$, there is an integer $g(k_1,k_2,k_3)$ such that every strongly connected digraph with chromatic number greater than $g(k_1,k_2,k_3)$ contains a subdivision of $B(k_1,k_2;k_3)$. As evidence, we prove this conjecture for $k_2=1$ (and $k_1, k_3$ arbitrary).
Published: 2018
Full Text: View/download PDF

18. On the Minimum Size of an Identifying Code Over All Orientations of a Graph

Author: Nathann Cohen, Frédéric Havet, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Applied Mathematics, Digraph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Theoretical Computer Science, Combinatorics, identifying code, orientations, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, NP-complete, Mathematics
Abstract: If $G$ be a graph or a digraph, let $\mathrm{id}(G)$ be the minimum size of an identifying code of $G$ if one exists, and $\mathrm{id}(G)=+\infty$ otherwise. For a graph $G$, let $\mathrm{idor}(G)$ be the minimum of $\mathrm{id}(D)$ overall orientations $D$ of $G$. We give some lower and upper bounds on $\mathrm{idor}(G)$. In particular, we show that $\mathrm{idor}(G)\leqslant \frac{3}{2} \mathrm{id}(G)$ for every graph $G$. We also show that computing $\mathrm{idor}(G)$ is NP-hard, while deciding whether $\mathrm{idor}(G)\leqslant |V(G)|-k$ is polynomial-time solvable for every fixed integer $k$.
Published: 2018
Full Text: View/download PDF

19. Tournaments and Semicomplete Digraphs

Author: Jørgen Bang-Jensen, Frédéric Havet, Bang-Jensen, Jørgen, Gutin, Gregory, COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Class (set theory), Mathematics::Combinatorics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Combinatorics, Range (mathematics), Cover (topology), 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Order (group theory), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Superclass, Mathematics
Abstract: The class of tournaments is by far the most well-studied class of digraphs with many deep and important results. Since Moon’s pioneering book in 1968 [146], the study of tournaments and their properties has flourished and research on tournaments is still a very active area. Often this research deals with the superclass of semicomplete digraphs which are digraphs with no pair of non-adjacent vertices (that is, contrary to tournaments, we allow directed cycles of length 2). In this chapter we cover a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones. In order to stimulate further research, we not only list a number of open problems, but also give a number of proofs which illustrate the diversity of proof techniques that have been applied. These range from elementary to quite advanced.
Published: 2018
Full Text: View/download PDF

20. Steinberg-like theorems for backbone colouring

Author: Frédéric Havet, Júlio Araújo, Mathieu Schmitt, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Lyon (ENS Lyon), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon), and CNRS-FUNCAP GAIATO
Subjects: Graph colouring, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Planar Graph, Combinatorics, symbols.namesake, Steinberg's Conjecture, Subgroup, Graph power, Graph minor, Discrete Mathematics and Combinatorics, Graph toughness, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Connected component, Graph Colouring, Applied Mathematics, 010102 general mathematics, Backbone Colouring, Graph, Planar graph, New digraph reconstruction conjecture, Edge-transitive graph, 010201 computation theory & mathematics, symbols, Bound graph, Graph factorization
Abstract: A function f : V ( G ) → { 1 , … , k } is a (proper) k -colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1 , for every edge u v ∈ E ( G ) . The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k -colouring of G . Given a graph G and a subgraph H of G , a circular q -backbone k -colouring f of ( G , H ) is a k -colouring of G such that q ≤ ∣ f ( u ) − f ( v ) ∣ ≤ k − q , for each edge u v ∈ E ( H ) . The circular q -backbone chromatic number of a graph pair ( G , H ) , denoted CBC q ( G , H ) , is the minimum k such that ( G , H ) admits a circular q -backbone k -colouring. Inspired by Steinberg’s conjecture, we conjecture that if G is a planar graph containing no cycles on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 6 . In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 7 . Then, we prove that if H ⊆ G is a forest whose connected components are paths, then CBC 2 ( G , H ) ≤ 6 .
Published: 2018
Full Text: View/download PDF

21. On the Complexity of Compressing Two Dimensional Routing Tables with Order

Author: Joanna Moulierac, Frédéric Havet, Frédéric Giroire, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Discrete mathematics, Reduction (recursion theory), General Computer Science, Applied Mathematics, Routing table, Order (ring theory), Approximation algorithm, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Computer Science Applications, Combinatorics, Integer, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Routing (electronic design automation), Mathematics
Abstract: Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications $$\mathcal {X}$$ , which are distinct pairs $$(s,t)\subseteq S\times T$$ , (typically S is the set of sources and T the set of destinations), and a port function $$\pi :\mathcal {X} \rightarrow P$$ where P is the set of ports. A routing list $$\mathcal {R}$$ is an ordered list of triples which are of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ with $$s\in S$$ , $$t\in T$$ and $$p\in P$$ . It routes the communication (s, t) to the port $$r(s,t) =p$$ which appears on the first triple in the list $$\mathcal {R}$$ that is of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ . If $$r(s,t)=\pi (s,t)$$ , then we say that (s, t) is properly routed by $$\mathcal {R}$$ and if all communications of $$\mathcal {X}$$ are properly routed, we say that $$\mathcal {R}$$ emulates $$(\mathcal {X}, \pi )$$ . The aim is to find a shortest routing list emulating $$(\mathcal {X}, \pi )$$ . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication $$\mathcal {X}$$ , a port function $$\pi $$ and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating $$(\mathcal {X}, \pi )$$ of size at most k (resp. $$|\mathcal {X}| -k$$ ). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. $$|P|=2$$ ), $$\mathcal {X}=S\times T$$ and $$|S|=|T|$$ .
Published: 2018
Full Text: View/download PDF

22. Bispindle in strongly connected digraphs with large chromatic number

Author: Raul Lopes, William Lochet, Frédéric Havet, Nathann Cohen, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institut National de Recherche en Informatique et en Automatique (Inria), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Strongly connected component, business.industry, Applied Mathematics, Digraph, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Integer, 010201 computation theory & mathematics, chromatic number, subdivision, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Chromatic scale, business, Mathematics, Subdivision
Abstract: A ( k 1 + k 2 )-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We investigate generalisations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any ( 3 + 0 )-bispindle or ( 2 + 2 )-bispindle. Then we show that for any k, there exists γ k such that every strongly connected digraph with chromatic number greater than γ k contains a ( 2 + 1 )-bispindle with the (y, x)-dipath and one of the (x, y)-dipaths of length at least k.
Published: 2017
Full Text: View/download PDF

23. Out-degree reducing partitions of digraphs

Author: Joergen Bang-Jensen, Frédéric Havet, Anders Yeo, Stéphane Bessy, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Danish research council, grant number 1323-00178B, Labex UCN@Sophia, OSMO project, Occitanie regional council, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), General Computer Science, Maximum out-degree reducing partition, Polynomial algorithm, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Integer, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Mathematics, NP-complete, Discrete mathematics, Mathematics::Combinatorics, 2-partition, 010102 general mathematics, Out degree, Digraph, 010201 computation theory & mathematics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: Let $k$ be a fixed integer. We determine the complexity of finding a $p$-partition $(V_1, \dots, V_p)$ of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by $V_i$, ($1\leq i\leq p$) is at least $k$ smaller than the maximum out-degree of $D$. We show that this problem is polynomial-time solvable when $p\geq 2k$ and ${\cal NP}$-complete otherwise. The result for $k=1$ and $p=2$ answers a question posed in \cite{bangTCS636}. We also determine, for all fixed non-negative integers $k_1,k_2,p$, the complexity of deciding whether a given digraph of maximum out-degree $p$ has a $2$-partition $(V_1,V_2)$ such that the digraph induced by $V_i$ has maximum out-degree at most $k_i$ for $i\in [2]$. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition $(V_1,V_2)$ such that each vertex $v\in V_i$ has at least as many neighbours in the set $V_{3-i}$ as in $V_i$, for $i=1,2$ is ${\cal NP}$-complete. This solves a problem from \cite{kreutzerEJC24} on majority colourings., 11 pages, 1 figure
Published: 2017
Full Text: View/download PDF

24. Bipartite spanning sub(di)graphs induced by 2-partitions

Author: Jørgen Bang-Jensen, Anders Yeo, Frédéric Havet, Stéphane Bessy, University of Southern Denmark (SDU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Occitanie regional council. Grant Number: OSMO- Labex UCN©Sophia- Danish Research Council. Grant Number: 1323‐00178B, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: FOS: Computer and information sciences, Strongly connected component, Discrete Mathematics (cs.DM), eulerian, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 2-partition, spanning bipartite subdigraph, Combinatorics, symbols.namesake, Computer Science::Discrete Mathematics, Spanning bipartite subdigraph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Nuclear Experiment, Eulerian, Mathematics, Mathematics::Combinatorics, Minimum out-degree, 2-partition, 010102 general mathematics, strong spanning subdigraph, Strong spanning subdigraph, Digraph, Eulerian path, Graph, Vertex (geometry), 010201 computation theory & mathematics, Bipartite graph, symbols, minimum out-degree, Geometry and Topology, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: For a given $2$-partition $(V_1,V_2)$ of the vertices of a (di)graph $G$, we study properties of the spanning bipartite subdigraph $B_G(V_1,V_2)$ of $G$ induced by those arcs/edges that have one end in each $V_i$. We determine, for all pairs of non-negative integers $k_1,k_2$, the complexity of deciding whether $G$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_i$ has at least $k_i$ (out-)neighbours in $V_{3-i}$. We prove that it is ${\cal NP}$-complete to decide whether a digraph $D$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_1$ has an out-neighbour in $V_2$ and each vertex in $V_2$ has an in-neighbour in $V_1$. The problem becomes polynomially solvable if we require $D$ to be strongly connected. We give a characterisation, based on the so-called strong component digraph of a non-strong digraph of the structure of ${\cal NP}$-complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set the problem becomes ${\cal NP}$-complete even for strong digraphs. A further result is that it is ${\cal NP}$-complete to decide whether a given digraph $D$ has a $2$-partition $(V_1,V_2)$ such that $B_D(V_1,V_2)$ is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph., Comment: 17 pages, 4 figures
Published: 2017
Full Text: View/download PDF

25. Identifying codes for infinite triangular grids with a finite number of rows

Author: Frédéric Havet, Rudini Menezes Sampaio, Rennan Dantas, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), INRIA Sophia Antipolis - I3S, FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), and FUNCAP-CNRS project GAIATO
Subjects: Vertex (graph theory), Discrete mathematics, grille, Discharging method, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Triangular grid, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, grid, Graph, Theoretical Computer Science, Combinatorics, identifying code, 010201 computation theory & mathematics, méthode de déchargement, code identifiant, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, discharging method, Row, Finite set, Minimum density, Mathematics
Abstract: Let $\mathcal{G}_T$ be the infinite triangular grid. For any positive integer $k$, we denote by $T_k$ the subgraph of $\mathcal{G}_T$ induced by the vertex set $\{(x,y)\in\mathbb{Z}\times[k]\}$.A set $C\subset V(G)$ is an {\it identifying code} in a graph $G$ if for all $v\in V(G)$, $N[v]\cap C\neq \emptyset$, and for all $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, where $N[x]$ denotes the closed neighborhood of $x$ in $G$.The minimum density of an identifying code in $G$ is denoted by $d^*(G)$.In this paper, we prove that $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ and $d^*(T_k)=1/4+1/(4k)$ for every $k\geq 7$ odd. Moreover, we prove that $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ for every $k\geq 8$ even.; Soit $\mathcal{G}_T$ la grille triangulaire infinie. Pour pout entier strictement positif $k$, nous notons $T_k$ le sous-graphe de $\mathcal{G}_T$ induit par l'ensemble des sommets $\{(x,y)\in\mathbb{Z}\times[k]\}$.Un ensemble $C\subset V(G)$ est un {\it code identifiant} d'un graphe $G$ si pour tout $v\in V(G)$, $N[v]\cap C\neq \emptyset$, et pour tout $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, o\`u $N[x]$ est le voisinage ferm\'e de $x$ dans $G$.La densit\'e minimum d'un code identifiant de $G$ est not\'ee $d^*(G)$.Dans ce rapport, nous montrons que $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ et $d^*(T_k)=1/4+1/(4k)$ pour tout $k\geq 7$ impair. De plus, nous montrons que $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ pour tout $k\geq 8$ pair.
Published: 2016
Full Text: View/download PDF

26. Finding an induced subdivision of a digraph

Author: Frédéric Havet, Nicolas Trotignon, Jørgen Bang-Jensen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741)., Electronic Notes on Discrete Mathematics, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and INRIA
Subjects: FOS: Computer and information sciences, Polynomial, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 3-SAT, Computer Science::Discrete Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Mathematics, Subdivision, Discrete mathematics, Mathematics::Combinatorics, business.industry, Applied Mathematics, 020206 networking & telecommunications, Digraph, Graph, NP-completeness, induced paths and cycles, 010201 computation theory & mathematics, Combinatorics (math.CO), linkings, business, Computer Science(all), Computer Science - Discrete Mathematics, digraphs
Abstract: International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
Published: 2012
Full Text: View/download PDF

27. Choosability of the square of planar subcubic graphs with large girth

Author: Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Planar graph, Theoretical Computer Science, Choice number, Combinatorics, symbols.namesake, Planar, List colouring, 010201 computation theory & mathematics, Square of a graph, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Bounded density, Mathematics
Abstract: International audience; We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.
Published: 2009
Full Text: View/download PDF

28. Finding good 2-partitions of digraphs I. Hereditary properties

Author: Frédéric Havet, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Labex UCN@Sophia, Sophia Antipolis, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Strongly connected component, General Computer Science, polynomial, 0102 computer and information sciences, Vertex partition, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, semicomplete digraph, out-branching, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, Partition (number theory), Tournament, splitting digraphs, 0101 mathematics, Mathematics, minimum degree, NP-complete, Discrete mathematics, oriented, 2-partition, 010102 general mathematics, acyclic, Digraph, feedback vertex set, partition, tournament, Has property, 010201 computation theory & mathematics, Feedback vertex set
Abstract: We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k 1 , k 2 , whether a given digraph has a vertex partition into two digraphs D 1 , D 2 such that | V ( D i ) | ź k i and D i has property P i for i = 1 , 2 when P 1 ź H and P 2 ź H ź E . We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P 1 and P 2 are in E is determined in the companion paper 2.
Published: 2016
Full Text: View/download PDF

29. Subidvisions de cycles orientés dans les graphes dirigés de fort nombre chromatique

Author: Nicolas Nisse, Frédéric Havet, Nathann Cohen, William Lochet, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), LRI-GALAC, ANR-13-BS02-0007,Stint,Structures Interdites(2013), École normale supérieure de Lyon (ENS de Lyon), LRI - CNRS, University Paris-Sud, LIP - ENS Lyon, INRIA Sophia Antipolis - I3S, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), École normale supérieure - Lyon (ENS Lyon), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Strongly connected component, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Orientation (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Chromatic scale, 0101 mathematics, Mathematics, Subdivision, Mathematics::Combinatorics, business.industry, 010102 general mathematics, Digraph, Arbitrarily large, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract: An {\it oriented cycle} is an orientation of a undirected cycle.We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number.In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).; Un {\it cycle orienté} est l'orientation d'un cycle. Nous prouvons que pour tout cycle orienté $C$ il existe des graphes dirigés sans subdivisions de $C$ (en tant que sous graphe) et de nombre chromatique arbitrairement grand. Par ailleurs, nous prouvons que pour tout cycle a deux bloques, tout graphe dirigé fortement connexe de nombre chromatique suffisamment grand contient une subdivision de $C$. Nous prouvons aussi un resultat semblable sur le cycle antidirigé de taille quatre (avec deux sommets de degré sortant $2$ et deux sommets de degré entrant $2$).
Published: 2016
Full Text: View/download PDF

30. Minimum-Density Identifying Codes in Square Grids

Author: Frédéric Havet, Myriam Preissmann, Marwane Bouznif, Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Riccardo Dondi, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and INRIA Sophia Antipolis - I3S
Subjects: Square tiling, Discrete mathematics, Discharging method, Neighbourhood (graph theory), square grid, 010103 numerical & computational mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, identifying code, 010201 computation theory & mathematics, discharging method, 0101 mathematics, Minimum density, Mathematics
Abstract: An identifying code in a graph $G$ is a subset of vertices with the property that for each vertex $v \in V(G)$, the collection of elements of $C$ at distance at most $1$ from $v$ is non-empty and distinct from the collection of any other vertex. We consider the minimum density $d^*({\cal S}_k)$ of an identifying code in the square grid ${\cal S}_k$ of height $k$ (i.e. with vertex set $ \mathbb{Z} \times \{1, \dots , k\}$).Using the Discharging Method, we prove $\displaystyle \frac{7}{20} + \frac{1}{20k} \leq d^*({\cal S}_k) \leq \min \left\{\frac{2}{5}, \frac{7}{20} + \frac{3}{10k} \right\}$, and $\displaystyle d^*({\cal S}_3) =\frac{3}{7}$.
Published: 2016
Full Text: View/download PDF

31. Complexity of greedy edge-colouring

Author: A. Karolinna Maia, Min-Li Yu, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Federal do Ceará = Federal University of Ceará (UFC), University of the Fraser Valley (UFV), CNRS-FUNCAP GAIATO, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Mathematical optimization, General Computer Science, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Data structure, 01 natural sciences, Graph, law.invention, Combinatorics, Greedy coloring, 010201 computation theory & mathematics, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, NP-complete, Greedy algorithm, Computer Science(all), Mathematics
Abstract: International audience; The Grundy index of a graph G = (V, E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = (V, E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.
Published: 2015
Full Text: View/download PDF

32. Finding a subdivision of a digraph

Author: Frédéric Havet, A. Karolinna Maia, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Polynomial, General Computer Science, business.industry, 010102 general mathematics, Digraph, 0102 computer and information sciences, Directed graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, 0101 mathematics, business, Subdivision, Mathematics
Abstract: International audience; We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.
Published: 2015
Full Text: View/download PDF

33. Detection number of bipartite graphs and cubic graphs

Author: Nagarajan Paramaguru, Rathinaswamy Sampathkumar, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Mathematics Wing, Directorate of Distance Education [India], Annamalai University, Mathematics Section [India], ANR-09-BLAN-0373,GraTel(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), and INRIA
Subjects: Discrete mathematics, General Computer Science, Foster graph, cubic graph, Neighbourhood (graph theory), bipartite grap, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Gray graph, NP-completeness, Theoretical Computer Science, detectable coloring, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Edge-transitive graph, Graph power, Bipartite graph, Discrete Mathematics and Combinatorics, Bound graph, Graph toughness, Mathematics
Abstract: For a connected graph G of order |V(G)| ≥ 3 and a k-labelling c : E(G) → {1,2, . . . ,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1, ℓ2, . . . , ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-labelling is the detection number of G. In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is 2. We also show that the detection number of every bipartite graph of minimum degree at least 3 is at most 2. Finally, we give some sufficient condition for a cubic graph to have detection number 3.; Pour un graphe connexe G d'ordre |V(G)| ≥ 3 et un étiquetage c : E(G) → {1,2, . . . ,k} des arêtes de G, le code d'un sommet v de G est le k-uplet (ℓ1, ℓ2, . . . , ℓk), où ℓi est le nombre d'arêtes incidentes à v qui sont étiquetées i. Le k-étiquetage c est détectable si, quels que soient deux sommets adjacents de G, leurs codes sont distincts. Le plus petit entier strictement positif k pour lequel G a un k-étiquetage détectable est l'indice de détection det(G) de G. Dans ce rapport, nous montrons qu'il est NP-complet de décider si l'indice de détection d'une graphe cubique vaut 2. Nous montrons également que l'indice de détection de tout graphe biparti de degré minimum au moins 3 est au plus 2. Enfin, nous donnons des conditions suffisantes pour qu'un graphe cubique soit d'indice de détection 3.
Published: 2014
Full Text: View/download PDF

34. (Circular) backbone colouring: forest backbones in planar graphs

Author: Ioan Todinca, Mathieu Liedloff, Frédéric Havet, Andrew D. King, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Department of computer science [Burnaby], Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
Subjects: Discrete mathematics, Vertex (graph theory), Spanning tree, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Galaxy, Planar graph, Combinatorics, symbols.namesake, Planar, 010201 computation theory & mathematics, symbols, Discrete Mathematics and Combinatorics, Chromatic scale, 0101 mathematics, NP-complete, Undirected graph, Mathematics
Abstract: International audience; Consider an undirected graph $G$ and a subgraph $H$ of $G$, on the same vertex set. The {\it $q$-backbone chromatic number} $\BBC_q(G,H)$ is the minimum $k$ such that $G$ can be properly coloured with colours from $\{1, \dots, k\}$, and moreover for each edge of $H$, the colours of its ends differ by at least $q$. In this paper we focus on the case when $G$ is planar and $H$ is a forest. We give a series of NP-hardness results as well as upper bounds for $\BBC_q(G,H)$, depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.
Published: 2014
Full Text: View/download PDF

35. List circular backbone colouring

Author: Andrew D. King, Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Pacific Institute for the Mathematical Sciences (PIMS), University of Calgary, Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Department of computer science [Burnaby], INRIA, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Departments of mathematics and computing science, and University of Calgary-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, Critical graph, General Computer Science, Discrete Mathematics, Graph colouring, General problem, Minimum distance, Graph theory, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Metric space, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Bounded function, Graph Theory, Discrete Mathematics and Combinatorics, Chromatic scale, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Graph Theory, A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.
Published: 2014
Full Text: View/download PDF

36. On the Grundy and b-chromatic numbers of a graph

Author: Frédéric Havet, Leonardo Sampaio, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, General Computer Science, Applied Mathematics, 010102 general mathematics, Greedy Colouring, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Vertex (geometry), NP-completeness, Combinatorics, 010201 computation theory & mathematics, Grundy number, Fixed Parameter Complexity, Bipartite graph, Online Colouring, Chromatic scale, 0101 mathematics, Greedy algorithm, Colouring, Mathematics
Abstract: The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertexes of G. The b-chromatic number of a graph G, denoted by χ b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|−k or if χ b (G)≥|V(G)|−k are fixed parameter tractable problems with respect to the parameter k.
Published: 2013

37. The game Grundy number of graphs

Author: Xuding Zhu, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics [Jinhua], Zhejiang Normal University, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Control and Optimization, Applied Mathematics, Nim, 010102 general mathematics, 0102 computer and information sciences, trees, game Grundy number, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Vertex (geometry), Combinatorics, Computational Theory and Mathematics, Alice and Bob, 010201 computation theory & mathematics, Grundy number, Theory of computation, Grundy's game, Colouring game, Discrete Mathematics and Combinatorics, 0101 mathematics, Game tree, partial 2-trees, Mathematics
Abstract: International audience; Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.
Published: 2013
Full Text: View/download PDF

38. Backbone colouring: Tree backbones with small diameter in planar graphs

Author: Ana Silva, Rudini Menezes Sampaio, Frédéric Havet, Victor Campos, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Small diameter, Spanning tree, Conjecture, General Computer Science, Spanning subgraph, Shortest-path tree, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, symbols, Mathematics
Abstract: Given a graph G and a spanning subgraph T of G , a backbone k -colouring for ( G , T ) is a mapping c : V ( G ) → { 1 , … , k } such that | c ( u ) − c ( v ) | ≥ 2 for every edge u v ∈ E ( T ) and | c ( u ) − c ( v ) | ≥ 1 for every edge u v ∈ E ( G ) ∖ E ( T ) . The backbone chromatic number B B C ( G , T ) is the smallest integer k such that there exists a backbone k -colouring of ( G , T ) . In 2007, Broersma et al. [2] conjectured that B B C ( G , T ) ≤ 6 for every planar graph G and every spanning tree T of G . In this paper, we prove this conjecture when T has diameter at most four.
Published: 2013
Full Text: View/download PDF

39. Oriented trees in digraphs

Author: Cláudia Linhares Sales, Louigi Addario-Berry, Stéphan Thomassé, Frédéric Havet, Bruce Reed, Department of Mathematics and Statistics [Montréal], McGill University = Université McGill [Montréal, Canada], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Discrete mathematics, Conjecture, 010102 general mathematics, Digraph, 0102 computer and information sciences, Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Integer, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Order (group theory), Tree (set theory), 0101 mathematics, Mathematics
Abstract: Let f ( k ) be the smallest integer such that every f ( k ) -chromatic digraph contains every oriented tree of order k . Burr proved f ( k ) ≤ ( k − 1 ) 2 in general, and he conjectured f ( k ) = 2 k − 2 . Burr also proved that every ( 8 k − 7 ) -chromatic digraph contains every antidirected tree. We improve both of Burr’s bounds. We show that f ( k ) ≤ k 2 / 2 − k / 2 + 1 and that every antidirected tree of order k is contained in every ( 5 k − 9 ) -chromatic digraph. We make a conjecture that explains why antidirected trees are easier to handle. It states that if | E ( D ) | > ( k − 2 ) | V ( D ) | , then the digraph D contains every antidirected tree of order k . This is a common strengthening of both Burr’s conjecture for antidirected trees and the celebrated Erdős-Sos Conjecture. The analogue of our conjecture for general trees is false, no matter what function f ( k ) is used in place of k − 2 . We prove our conjecture for antidirected trees of diameter 3 and present some other evidence for it. Along the way, we show that every acyclic k -chromatic digraph contains every oriented tree of order k and suggest a number of approaches for making further progress on Burr’s conjecture.
Published: 2013
Full Text: View/download PDF

40. On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems

Author: Christophe Paul, Sylvain Guillemot, Frédéric Havet, Anthony Perez, Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
Subjects: Vertex (graph theory), Discrete mathematics, General Computer Science, Applied Mathematics, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Quotient graph, Computer Science Applications, Modular decomposition, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Cograph, Hereditary property, Graph property, Time complexity, Mathematics
Abstract: Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property ź consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property ź. In the źedge-completion problem, the set F is constrained to be disjoint from E; in the źedge-deletion problem, F is a subset of E; no constraint is imposed on F in the źedge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171---176, 1996; Fellows et al. in FCT, pp. 312---321, 2007; Heggernes et al. in STOC, pp. 374---381, 2007). When parameterized by the size k of the set F, it has been proved that if ź is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three ź edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171---176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (Gź,kź) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlstrom answered this question negatively (Kratsch and Wahlstrom in IWPEC, pp. 264---275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlstrom asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P4-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the Pl-free edge-deletion and the Cl-free edge-deletion problems for lź7 and lź4 respectively. Indeed, if they exist, then NP⊆coNP/poly.
Published: 2013
Full Text: View/download PDF

41. Enumerating the edge-colourings and total colourings of a regular graph

Author: Frédéric Havet, Stéphane Bessy, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR, Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), INRIA, and Bessy, Stéphane
Subjects: Factor-critical graph, Control and Optimization, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Distance-regular graph, Combinatorics, Graph power, Discrete Mathematics and Combinatorics, Mathematics, Discrete mathematics, 021103 operations research, Applied Mathematics, Voltage graph, Quartic graph, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, Cubic graph, Regular graph, Tutte polynomial, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of $k$-edge-colourings of a connected $k$-regular graph on $n$ vertices is $k\cdot((k-1)!)^{n/2}$. Our proof is constructive and leads to a branching algorithm enumerating all the $k$-edge-colourings of a connected $k$-regular graph in time $O^*(((k-1)!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm to enumerate all the $3$-edge-colourings of a connected cubic graph in time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space. This improves the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3\cdot 2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.
Published: 2012
Full Text: View/download PDF

42. On Spanning Galaxies in Digraphs

Author: Frédéric Havet, Daniel Gonçalves, Stéphan Thomassé, Alexandre Pinlou, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Arborescence, Parameterized complexity, 0102 computer and information sciences, Astrophysics::Cosmology and Extragalactic Astrophysics, Star (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, Discrete Mathematics and Combinatorics, 0101 mathematics, Computer Science::Data Structures and Algorithms, Astrophysics::Galaxy Astrophysics, Mathematics, Minimum degree spanning tree, Discrete mathematics, Mathematics::Combinatorics, Applied Mathematics, Arboricity, 010102 general mathematics, Spanning galaxy, Digraph, Directed graph, Directed star arboricity, Galaxy, Even strong subdigraph, 010201 computation theory & mathematics, Fixed parameter tractable, Algorithms
Abstract: In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph D has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem is equivalent to the problem of deciding whether a strong digraph has a strong subdigraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph D, which is the minimum number of galaxies needed to cover all the arcs of D. We show in particular that dst(D)@[email protected](D)+1 for every digraph D and that dst(D)@[email protected](D) for every acyclic digraph D.
Published: 2012
Full Text: View/download PDF

43. Griggs and Yeh's Conjecture and L(p,1)-labelings

Author: Bruce Reed, Jean-Sébastien Sereni, Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Graph labeling, Conjecture, generalized coloring, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.1: Graph labeling, General Mathematics, 010102 general mathematics, graph labeling, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, Integer, 010201 computation theory & mathematics, channel assignment, graph coloring, Graph coloring, 0101 mathematics, Mathematics
Abstract: An $L(p,1)$-labeling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices $x$ and $y$ in the graph. The span of an $L(p,1)$-labeling $f$ is the difference between the largest and the smallest labels used by $f$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer $p$ there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer $p$, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.
Published: 2012
Full Text: View/download PDF

44. Weighted Improper Colouring

Author: Jean-Claude Bermond, Remigiusz Modrzejewski, Júlio Araújo, Frédéric Havet, Frédéric Giroire, Dorian Mazauric, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), This work was partially supported by r'egion PACA and ANR International Taiwan GRATEL (ANR-09-BLAN-0373)., ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Models for the performance analysis and the control of networks (MAESTRO), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), région PACA, and INRIA
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Weight function, Heuristic (computer science), Frequency assignment, Graph colouring, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Partition problem, interference, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Interference (wave propagation), 01 natural sciences, Square (algebra), radio networks, Theoretical Computer Science, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Integer, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Chromatic scale, Integer programming, Mathematics, Discrete mathematics, graph colouring, Wireless network, Hexagonal crystal system, 020206 networking & telecommunications, Frequency assignment problem, Graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, frequency assignment, Node (circuits), Voronoi diagram, improper colouring
Abstract: In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two end-vertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$-improper $k$-colouring of $(G,w)$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$. We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovász's Theorem for the weighted $t$-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either one or $M$, for a sufficiently large $M$. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted $t$-improper chromatic number for all values of $t$. Finally, we model the problem using integer linear programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.; Dans ce papier, nous étudions un nouveau problème de coloration motivé par un problème pratique d'allocation de fréquences. Dans les réseaux sans-fil, un n\oe{}ud interfère avec d'autres, à un niveau dépendant de nombreux paramètres : la distance entre les n\oe{}uds, la topographie physique, les obstacles, etc. Nous modélisons cela par un graphe arête-valué $(G,w)$ oú le poids d'une arête représente le bruit (ou l'interférence) entre ces deux extrémités. L'interférence totale au niveau d'un n\oe{}ud est alors la somme de tous les bruits entre ce n\oe{}ud et les autres n\oe{}uds émettant avec la même fréquence. Une $k$-coloration $t$-impropre pondérée de $(G,w)$ est une $k$-coloration des n\oe{}uds de $G$ (assignation de $k$ fréquences) telle que l'interférence à chaque n\oe{}ud n'excède pas un certain seuil $t$. Dans ce papier, nous étudions le problème de la coloration impropre pondérée qui consiste à déterminer le nombre chromatique $t$-impropre pondéré d'un graphe arête-valué $(G,w)$, qui est le plus petit entier $k$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous considérons également le problème Threshold Improper Colouring (le problème dual) qui, étant donné un nombre de couleurs (fréquences), consiste à déterminer le plus petit réel $t$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous montrons d'abord des bornes supérieures générales; en particulier nous prouvons une généralisation du théorème de Lovász pour le problème du nombre chromatique $t$-impropre pondéré. Nous montrons ensuite comment transformer une instance du probléme Threshold Improper Colouring en une instance équivalente avec des poids $1$ ou $M$, pour une valeur de $M$ suffisamment grande. Motivé par l'origine du problème, nous étudions un modèle d'interférence particulier pour différentes grilles (carrée, triangulaire, hexagonale) oú un n\oe{}ud produit un bruit d'intensité $1$ pour ses voisins et un bruit d'intensité $1/2$ pour les n\oe{}uds à distance deux. Nous montrons le nombre chromatique $t$-impropre pour toutes les valeurs de $t$. Enfin, nous modélisons le problème par des programmes linéaires en nombres entiers, nous proposons des heuristiques et des algorithmes exactes d'énumération par la technique du Branch-and-Bound. Nous les testons pour des graphes aléatoires ressemblant à des réseaux cellulaires, à savoir des tessellations de Poisson-Voronoi.
Published: 2011
Full Text: View/download PDF

45. Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

Author: Frédéric Havet, Nathann Cohen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Degree (graph theory), 010102 general mathematics, Discharging method, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract: A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment $${L:V(G)\mapsto 2^{\mathbb N}}$$, there exists a 2-frugal (resp. linear) colouring c of G such that $${c(v) \in L(v)}$$ for all $${v\in V(G)}$$. If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all $${v\in V(G)}$$, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.
Published: 2011

46. 5-colouring graphs with 4 crossings

Author: Rok Erman, Ondřej Pangrác, Bernard Lidický, Frédéric Havet, Departement of Mathematics [Slovenia], University of Ljubljana, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institute for Theoretical Computer Science (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Block graph, Clique-sum, General Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Clique graph, 01 natural sciences, 1-planar graph, Simplex graph, Treewidth, Combinatorics, 010201 computation theory & mathematics, Split graph, Crossing number (graph theory), 0101 mathematics, Mathematics
Abstract: International audience; We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948-2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.
Published: 2011
Full Text: View/download PDF

47. Improper colouring of weighted grid and hexagonal graphs

Author: Cláudia Linhares Sales, Florian Huc, Frédéric Havet, Jean-Claude Bermond, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Centre Universitaire d'Informatique, Université de Genève (UNIGE), Laboratórios de PesquIsa em ComputAção (LIA), Universidade Federal do Ceará = Federal University of Ceará (UFC), ANR-09-BLAN-0373,GraTel(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université de Genève = University of Geneva (UNIGE)
Subjects: Discrete mathematics, 021103 operations research, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Approximation algorithm, 0102 computer and information sciences, 02 engineering and technology, Complete coloring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Brooks' theorem, Greedy coloring, Combinatorics, Edge coloring, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Graph coloring, Fractional coloring, Mathematics, List coloring
Abstract: International audience; We study a weighted improper colouring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most k (the case k = 0 corresponds to a proper coloring). The objective is to minimize the number of colors. We propose approximation algorithms to compute such colouring for general graphs. We apply these to obtain good approximation ratio for grid and hexagonal graphs. Furthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same.
Published: 2010
Full Text: View/download PDF

48. Good edge-labelling of graphs

Author: Frédéric Havet, Júlio Araújo, Frédéric Giroire, Nathann Cohen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), European Project: 29470,IP-FP6-015964,AEOLUS(2005), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and INRIA
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Increasing paths, matching-cut, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.1: Graph labeling, graph theory, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.3: Network problems, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], edge-labelling, 01 natural sciences, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Partial k-tree, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Cograph, Mathematics, Discrete mathematics, Lévy family of graphs, Clique-sum, Applied Mathematics, 020206 networking & telecommunications, 1-planar graph, planar graphs, NP-completeness, Metric dimension, 010201 computation theory & mathematics, channel assignment, complexity, Graph product
Abstract: A good edge-labelling of a graph G is a labelling of its edges such that for any two distinct vertices u, v, there is at most one ( u , v ) -path with non-decreasing labels. This notion was introduced in [J.-C. Bermond, M. Cosnard, and S. Perennes. Directed acyclic graphs with unique path property. Technical Report RR-6932, INRIA, May 2009] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete. Finally, we give large classes of graphs admitting a good edge-labelling: C 3 -free outerplanar graphs, planar graphs of girth at least 6, subcubic { C 3 , K 2 , 3 } -free graphs.
Published: 2009
Full Text: View/download PDF

49. Spanning galaxies in digraphs

Author: Stéphan Thomassé, Frédéric Havet, Alexandre Pinlou, Daniel Gonçalves, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Jaroslav Nešetřil and André Raspaud, Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Strongly connected component, Mathematics::Combinatorics, Arborescence, Applied Mathematics, Arboricity, 010102 general mathematics, Digraph, 0102 computer and information sciences, Astrophysics::Cosmology and Extragalactic Astrophysics, Star (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Galaxy, Combinatorics, Stars, Cover (topology), 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Discrete Mathematics and Combinatorics, 0101 mathematics, Computer Science::Data Structures and Algorithms, Astrophysics::Galaxy Astrophysics, Mathematics
Abstract: A star is an arborescence in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. The directed star arboricity of a digraph D, denoted by dst ( D ) , is the minimum number of galaxies needed to cover A ( D ) . In this paper, we show that dst ( D ) ⩽ Δ ( D ) + 1 and that if D is acyclic then dst ( D ) ⩽ Δ ( D ) . These results are proved by considering the existence of spanning galaxies in digraphs. Thus, we study the problem of deciding whether a digraph D has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs.
Published: 2009
Full Text: View/download PDF

50. Complexity of $(p,1)$-Total Labelling

Author: Frédéric Havet, Stéphan Thomassé, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
Subjects: Total labelling, total colouring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], distance constrained colouring
Abstract: International audience; A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $\{0,\dots ,l\}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The minimum $l$ for which $G$ admits a $(p,1)$-total labelling is denoted by $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to calculate even for cubic bipartite graphs~\cite{MDSA94}. We assume $p\geq 2$ in this paper. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases.
Published: 2009
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Publication Type

Journal

Database

Publisher

57 results on '"Frédéric Havet"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources