PUBLICATIONS OF MARIO VALENCIA-PABON

Preprints

On the total chromatic number of the direct product of cycles and complete graphs (with Diane Castonguay, Celina M.H. de Figueiredo, Luis A.B. Kowada, Caroline S. R. Patrão, Diana Sasaki). December 2021.
On the diameter of Schrijver graphs (with Agustina V. Ledezma, Adrián Pastine, Pablo Torres). December, 2021.
On restricted completions of chordal and trivially perfect graphs (with Mitre Dourado, Luciano Grippo). April, 2022.

Journals

The rotations distance of brooms (with Jean Cardinal, Lionel Pournin). To appear in European Journal of Combinatorics, 2023.
Diameter estimates for graph associahedra (with Jean Cardinal, Lionel Pournin). Annals of Combinatorics, Vol. 26, pp. 873-902, 2022.
On total and edge coloring of some Kneser graphs (with Celina M.H. de Figueiredo, Caroline S. R. Patrão, Diana Sasaki). Journal of Combinatorial Optimization, Vol. 44, pp. 119-135, 2022.
On the P3-hull number of Kneser graphs (with Luciano N. Grippo, Adrián Pastine, Pablo Torres, Juan Carlos Vera). The Electronic Journal of Combinatorics, Vol. 28, Issue 3, 2021.
On the P3-hull number of Hamming graphs (with Boštjan Brešar). Discrete Applied Mathematics, Vol. 282, pp. 48-52, 2020.
A note on Homomorphisms of Kneser hypergraphs (with Flavia Bonomo-Braberman, Mitre Costa Dourado, Juan Carlos Vera Lizcano). Applied Mathematics and Computation, Vol. 366, 1 February 2020, Article 124764.
Independence number of products of Kneser graphs (with Boštjan Brešar). Discrete Mathematics, Vol. 342, pp. 1017-1027, 2019.
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid (with Liliana Alcon, Flavia Bonomo, Guillermo Duran, Marisa Gutierrez, Maria Pia Mazzoleni, Bernard Ries). Discrete Applied Mathematics, Vol. 234, pp. 12-21, 2018.
On the (k,i)-coloring of cacti and complete graphs (with Flavia Bonomo, Guillermo Duran, Ivo Koch). Ars Combinatoria, Vol. 137, pp. 317-333, 2018.
k-tuple colorings of the cartesian product of graphs (with Flavia Bonomo, Ivo Koch, Pablo Torres). Discrete Applied Mathematics, Vol. 245, pp. 177-182, 2018.
Shifts of the Stable Kneser Graphs and Hom-Idempotence (with Pablo Torres). European Journal of Combinatorics, Vol. 62, pp. 50-57, 2017.
Complexity of the cluster deletion problem on subclasses of chordal graphs (with Flavia Bonomo, Guillermo Duran). Theoretical Computer Science, Vol. 600, pp. 59-69, 2015.
b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (with Flavia Bonomo, Oliver Schaudt, Maya Stein). Algorithmica, Vol. 73, No 2, pp. 289-305, 2015.
The packing chromatic number of hypercubes (with Pablo Torres). Discrete Applied Mathematics, Vol. 190-191, pp. 127-140, 2015.
A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its applications to P4-sparse graphs (with Flavia Bonomo, Guillermo Duran, Amedeo Napoli). Information Processing Letters, Vol. 115, No. 6-8, pp. 600-603, 2015.
On the minimum sum coloring of P4-sparse graphs (with Flavia Bonomo). Graphs and Combinatorics, Vol. 30, No. 2, pp. 303-314, 2014.
Minimum sum set coloring of trees and line graphs of trees (with Flavia Bonomo, Guillermo Duran, Javier Marenco). Discrete Applied Mathematics, Vol. 159, No. 5, pp. 288-294, 2011.
On some problems on idomatic partitions and b-colorings of direct products of complete graphs. Matemática Contemporânea, special issue of the 4th Latin-American Workshop on Cliques in Graphs (invited talk), Vol. 39, pp. 93-100, 2010.
Idomatic partitions of direct products of complete graphs. Discrete Mathematics, Vol. 310, No. 5, pp. 1118-1122, 2010.
Minimum Sum Edge Colorings of Multicycles (with Jean Cardinal, Vlady Ravelomanana). Discrete Applied Mathematics, Vol. 158, No. 12, pp. 1216-1223, 2010.
On the b-coloring of cographs and P4-sparse graphs (with Flavia Bonomo, Guillermo Duran, Frédéric Maffray, Javier Marenco). Graphs and Combinatorics, Vol. 25, No. 2, pp. 153-167, 2009.
A distributed approximation algorithm for the minimum degree minimum weight spanning trees (with Christian Lavault). Journal of Parallel and Distributed Computing, Vol. 68, No. 2, pp. 200-208, 2008.
Independence and coloring properties of direct products of some vertex-transitive graphs (with Juan Vera). Discrete Mathematics, Vol. 306, No. 18, pp. 2275-2281, 2006.
On the diameter of Kneser graphs (with Juan Vera). Discrete Mathematics, Vol. 305, No. 1-3, pp. 383-385, 2005.
On approximating the b-chromatic number (with Sylvie Corteel, Juan Vera). Discrete Applied Mathematics, Vol. 146, No. 1, pp. 618-622, 2005.
Revisiting Tucker's algorithm to color circular arc graphs. SIAM Journal on Computing, Vol. 32, No. 4, pp. 1067-1072, 2003.
The permutation-path coloring problem on trees (with Sylvie Corteel, Danièle Gardy, Dominique Barth, Alain Denise). Theoretical Computer Science, Vol. 297, pp. 119-143, 2003.

In proceedings

On total coloring the direct product of complete graphs (with Diane Castonguay, Celina M.H. de Figueiredo, Luis A.B. Kowada, Caroline S. R. Patrão, Diana Sasaki). In Proc. of Lagos'21 symposium, Procedia Computer Science, Vol. 195, pp. 306-314, 2021.
On the diameter of Schrijver graphs (with Adrián Pastine, Pablo Torres). In Proc. of Lagos'21 symposium, Procedia Computer Science, Vol. 195, pp. 266-274, 2021.
Bounds on the Diameter of Graph Associahedra (with Jean Cardinal, Lionel Pournin). In Proc. of Lagos'21 symposium, Procedia Computer Science, Vol. 195, pp. 239-247, 2021.
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid (with Liliana Alcon, Flavia Bonomo, Guillermo Duran, Marisa Gutierrez, Maria Pia Mazzoleni, Bernard Ries). In Proc. of LAGOS'15 symposium, Electronic Notes in Discrete Mathematics, Vol. 50, pp. 249-254, 2015.
k-tuple chromatic number of the cartesian product of graphs (with Flavia Bonomo, Ivo Koch, Pablo Torres). In Proc. of LAGOS'15 symposium, Electronic Notes in Discrete Mathematics, Vol. 50, pp. 243-248, 2015.
b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (with Flavia Bonomo, Oliver Schaudt, Maya Stein). In Proc. of ISCO symposium, Lisboa (Portugal), LNCS 8596, pp. 100-111, March 5-7, 2014.
On the packing chromatic number of hypercubes (with Pablo Torres). In Proc. of LAGOS'13 symposium, Electronic Notes in Discrete Mathematics, Vol. 44, pp. 263-268, 2013.
On lower bounds for the b-chromatic number of connected bipartite graphs (with Mekkia Kouider). In Proc. of LAGOS'11 symposium, Electronic Notes in Discrete Mathematics, Vol. 37, pp. 399-404, 2011.
Sum coloring of P4-sparse graphs (with Flavia Bonomo). In Proc. of LAGOS'09 symposium, Electronic Notes in Discrete Mathematics, Vol. 35, pp. 293-298, 2009.
Sum set coloring of some block graphs (with Flavia Bonomo, Guillermo Duran, Javier Marenco). In Proc. of Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 195-198, 2009.
Chromatic Edge Strength of Some Multigraphs (with Jean Cardinal, Vlady Ravelomanana). In Proc. of LAGOS'07 symposium, Electronic Notes in Discrete Mathematics, Vol. 30, pp. 39-44, 2008.
Revisiting Tucker's Algorithm to Color Circular Arc Graphs. In Proc. of GRACO'01 symposium, Electronic Notes in Discrete Mathematics, Vol. 7, pp. 198-201, 2001.
On the Complexity of routing permutations on trees by arc-disjoint paths (with Sylvie Corteel, Danièle Gardy, Dominique Barth, Alain Denise). In proc. of LATIN 2000, LNCS 1776, pp. 308-317, Springer-Verlag, 2000.
Message scheduling on trees under a generalised line-communication model (with Dominique Barth). In Proc. of I-SPAN'99, pp. 10-15, IEEE CS Press, 1999.
Some results on an extension of the line communication model (with Dominique Barth). In Proc. of ALGOTEL'99, pp. 23-27, 1999.
Emulation dynamique de réseaux d'interconnexion. In Proc. of RENPAR'97, pp. 135-138, 1997.

Editorial work

Discrete Applied Mathematics, Vol. 281, 2020. LAGOS'17: IX Latin and American Algorithms, Graphs and Optimization Symposium, C.I.R.M. - Marseille, France. Edited by Frédérique Bassino, Flavia Bonomo-Braberman, Lionel Pournin and Mario Valencia-Pabon.
Electronic Notes in Discrete Mathematics, Vol. 62, 2017. Special issue of the LAGOS'17 - IX Latin and American Algorithms, Graphs and Optimization Symposium, CIRM, Luminy, Marseille, France. Edited by Frédérique Bassino, Flavia Bonomo, Lionel Pournin, Mario Valencia-Pabon and Juan Carlos Vera Lizcano.
Discrete Applied Mathematics, Vol. 164(2), 2014. LAGOS'11: Sixth Latin-American Algorithms, Graphs and Optimization Symposium, Bariloche, Argentina. Edited by Flavia Bonomo, Thomas Liebling, Javier Marenco, Jayme Szwarcfiter and Mario Valencia-Pabon.
Electronic Notes in Discrete Mathematics, Vol. 37, 2011. Special issue of the LAGOS'11 - VI Latin-American Algorithms, Graphs and Optimization Symposium, Bariloche, Argentina. Edited by Flavia Bonomo, Thomas Liebling, Javier Marenco, Jayme Szwarcfiter and Mario Valencia-Pabon.

Thesis

Variations of the graph coloring problem : theoretical aspects and algorithms. Habilitation à diriger des recherches. Université Paris-Nord. 2009.
Complexité du probléme de routage dans les réseaux de télécommunications : anneaux, arbres et grilles. Thèse de doctorat. Université Paris-Sud. 2000.

Technical Reports

A note on coloring powers of cycles (with Martín F. Jiménez). Technical Report, Los Andes University, Math. Dept., 2005.
On the chromatic polynomial of some graphs (with Camilo Garcia, Felipe Rincon). Technical Report, Los Andes University, Math. Dept., 2005.

Coauthors of my published papers:

Liliana Alcon, Dominique Barth, Flavia Bonomo-Braberman, Boštjan Brešar, Jean Cardinal, Diane Castonguay, Sylvie Corteel, Mitre Costa Dourado, Celina de Figueiredo, Alain Denise, Guillermo Duran, Danièle Gardy, Luciano Grippo, Marisa Gutierrez, Ivo Koch, Mekkia Kouider, Luis Kowada, Christian Lavault, Frédéric Maffray, Javier Marenco, Maria Pía Mazzoleni, Amedeo Napoli, Adrián Pastine, Caroline Patrão, Lionel Pournin, Vlady Ravelomanana, Bernard Ries, Diana Sasaki, Oliver Schaudt, Maya Stein, Pablo Torres, Juan Carlos Vera.