INFINIS is a French-Argentinean Laboratory (Laboratoire Internationale Associé) between Centre National de la Recherche Scientifique (CNRS) and Université Paris Diderot, on the one hand, and Consejo Nacional de Investigaciones Cientéficas y Técnicas (CONICET) and the Universidad de Buenos Aires, on the other. It is devoted to research in Computer Science. Specific focus is placed on formal methods, for modeling, verification and development of complex software artifacts.

Team on : Graph Theory and Combinatorial Optimization

Our research is focused on graph theory and combinatorial optimization. Particularly, in structural characterizations of graph classes, the study of the computational complexity of different graph problems, and the development of efficient algorithms for combinatorial optimization problems on graphs.

In France:

• Frederique Bassino (Univ. Paris-Nord)
• Pierre Charbit (Univ. Paris Diderot)
• Denis Cornaz (Univ. Paris Dauphine)
• Michel Habib (Univ. Paris Diderot)
• Frédéric Maffray (CNRS Grenoble INP)
• Gautier Stauffer (Grenoble INP)
• Mario Valencia-Pabon (Univ. Paris-Nord)
• Annegret Wagler (Univ. Blaise Pascal - Clermont-Ferrand II)

In Argentina:

• Flavia Bonomo (Univ. Buenos Aires and CONICET)
• Guillermo Durán (Univ. Buenos Aires and CONICET)
• Luciano Grippo (Univ. Gral. Sarmiento)
• Ivo Koch (Univ. Gral. Sarmiento)
• Nina Pardal (PhD Fellow CONICET at UBA. Advisors: Guillermo Durán and Mario Valencia-Pabon)
• Maria Pia Mazzoleni (Postdoc CONICET at UBA and UNLP)
• Mariano Rean (PhD Fellow CONICET at UBA. Advisor: Flavia Bonomo)
• Martín Safe (Univ. Nacional del Sur)
• Pablo Torres (CONICET and UNR)
  

Link to the site of the Argentinean group

Cooperation projects

• International Cooperation Project "Sorbonne Paris Cité": Analyse en moyenne de modules premiers dans la décomposition modulaire des graphes P₄-sparse et complexité algorithmique de certains problèmes d'optimisation dans ces graphes, 2015-2016.
  Leaders: Mario Valencia-Pabon, Flavia Bonomo.
• Chaire "Alicia Moreau", Université Paris Diderot, May-June 2015. Visit by Flavia Bonomo to LIAFA Université Paris Diderot, Paris, France. Collaborators in France: Michel Habib and Pierre Charbit.
• Math-AmSud (France-Argentina-Brazil-Chile): Algorithmic, Algebraic and Structural issues on coloring and matching theory of graphs, 2013-2015. International leader: Mario Valencia-Pabon. Leaders: Flavia Bonomo (Argentina), Marcia Cerioli (Brazil), Maya Stein (Chile).
• Math-AmSud (France-Argentina-Brazil): Variations of the graph coloring problem: theory, algorithms, and applications, 2010-2012. International leader: Guillermo Durán. Leaders: Mario Valencia-Pabon (France), Marcia Cerioli (Brazil).
• Project financed by Université Paris-Nord (France), "Bonus de Qualité et de Recherche" (BQR-UPN-2008) : Etude de quelques généralisations du problème de coloration des graphes : aspects théoriques, algorithmes et applications, 2009-2010. Leader: Mario Valencia-Pabon.

Joint papers

In press

1. Flavia Bonomo, Guillermo Durán, Ivo Koch, Mario Valencia-Pabon, "On the (k,i)-coloring of cacti and complete graphs", Ars Combinatoria [pdf]
2. Liliana Alcón, Flavia Bonomo, Guillermo Durán, Marisa Gutierrez, María Pía Mazzoleni, Bernard Ries, Mario Valencia-Pabon, "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid", Discrete Applied Mathematics [link] [pdf]

2015

1. Liliana Alcon, Flavia Bonomo, Guillermo Durán, Marisa Gutierrez, Pia Mazzoleni, Bernard Ries, Mario Valencia-Pabon, "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid (Extended abstract)", Electronic Notes in Discrete Mathematics, Volume 50, page 249--254 [link] [pdf]
2. Flavia Bonomo, Guillermo Durán, Amedeo Napoli, Mario Valencia-Pabon, "A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P_4-sparse graphs", Information Processing Letters, Volume 115, Number 6--8, page 600--603 [link] [pdf]
3. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "Clique-perfectness of complements of line graphs", Discrete Applied Mathematics, Volume 186, page 19--44 [link] [pdf]
4. Flavia Bonomo, Guillermo Durán, Mario Valencia-Pabon, "Complexity of the cluster deletion problem on subclasses of chordal graphs", Theoretical Computer Science, Volume 600, page 59--69 [link] [pdf]
5. Flavia Bonomo, Ivo Koch, Pablo Torres, Mario Valencia-Pabon, "k-tuple chromatic number of the cartesian product of graphs (Extended abstract)", Electronic Notes in Discrete Mathematics, Volume 50, page 243--248 [link] [pdf]
6. Flavia Bonomo, Oliver Schaudt, Maya Stein, Mario Valencia-Pabon, "b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs", Algorithmica, Volume 73, Number 2, page 289--305 [link] [pdf]

2014

1. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "Balancedness of some subclasses of circular-arc graphs", Discrete Mathematics and Theoretical Computer Science, Volume 16, Number 3, page 1--22 [link] [pdf]
2. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "Clique-perfectness and balancedness of some graph classes", International Journal of Computer Mathematics, Volume 91, Number 10, page 2118--2141 [link] [pdf]
3. Flavia Bonomo, Oliver Schaudt, Maya Stein, Mario Valencia-Pabon, "b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (Extended abstract)", Lecture Notes in Computer Science, Volume 8596, page 100--111 [link] [pdf]
4. Flavia Bonomo, Mario Valencia-Pabon, "On the Minimum Sum Coloring of P₄-sparse graphs", Graphs and Combinatorics, Volume 30, Number 2, page 303--314 [link] [pdf]

2013

1. Flavia Bonomo, Denis Cornaz, Tinaz Ekim, Bernard Ries "Perfectness of clustered graphs", Discrete Optimization, Volume 10, page 296--303 [link] [pdf]
2. Flavia Bonomo, Guillermo Durán, Martín Safe, Annegret Wagler, "On minimal forbidden subgraph characterizations of balanced graphs", Discrete Applied Mathematics, Volume 161, Number 13--14, page 1925--1942 [link] [pdf]

2011

1. Flavia Bonomo, Guillermo Durán, Javier Marenco, Mario Valencia-Pabon, "Minimum sum set coloring of trees and line graphs of trees", Discrete Applied Mathematics, Volume 159, Number 5, page 288--294 [link]
2. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "Clique-perfectness of complements of line graphs", Electronic Notes in Discrete Mathematics, Volume 37, page 327--332  [link]

2010

1. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "Balancedness of some subclasses of circular-arc graphs", Electronic Notes in Discrete Mathematics, Volume 36, page 1121--1128 [link]

2009

1. Flavia Bonomo, Guillermo Durán, Frédéric Maffray, Javier Marenco, Mario Valencia-Pabon, "On the b-coloring of cographs and P_4-sparse graphs", Graphs and Combinatorics, Volume 25, Number 2, page 153--167 [pdf] [link]
2. Flavia Bonomo, Guillermo Durán, Martin Safe, Annegret Wagler, "On minimal forbidden subgraph characterizations of balanced graphs", Electronic Notes in Discrete Mathematics, Volume 35, page 41--46 [pdf] [link]
3. Flavia Bonomo, Mario Valencia-Pabon, "Minimum Sum Coloring of P₄-sparse graphs", Electronic Notes in Discrete Mathematics, Volume 35, page 293--298 [pdf] [link]