Mario Valencia (Valencia-Pabon)

Preprints

1. On the spectrum and expansion of graph associahedra (with Ana Gargantini, Adrián Pastine, Pablo Torres).
   
   
2. Token sliding independent set reconfiguration on graphs with few $P_4$'s (with Lucía Busolini).
   
   
3. Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes (with Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza).
   
   
4. Exact distance Kneser graphs (with Agustina Ledezma, Adrián Pastine).
   
   

Journals

1. On the diameter of Schrijver graphs (with Agustina V. Ledezma, Adrián Pastine, Pablo Torres). Discrete Applied Mathematics, Vol. 350, pp. 15-30, 2024.
   
   
2. The rotations distance of brooms (with Jean Cardinal, Lionel Pournin). European Journal of Combinatorics, Vol. 118: 103877, 2024.
   
   
3. 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). RAIRO Operation Research, Vol. 58, Issue 2, pp. 1609-1632, 2024.
   
   
4. Diameter estimates for graph associahedra (with Jean Cardinal, Lionel Pournin). Annals of Combinatorics, Vol. 26, pp. 873-902, 2022.
   
   
5. 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.
   
   
6. 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.
   
   
7. On the P3-hull number of Hamming graphs (with Boštjan Brešar). Discrete Applied Mathematics, Vol. 282, pp. 48-52, 2020.
   
   
8. 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.
   
   
9. Independence number of products of Kneser graphs (with Boštjan Brešar). Discrete Mathematics, Vol. 342, pp. 1017-1027, 2019.
   
   
10. 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.
    
    
11. 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.
    
    
12. 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.
    
    
13. Shifts of the Stable Kneser Graphs and Hom-Idempotence (with Pablo Torres). European Journal of Combinatorics, Vol. 62, pp. 50-57, 2017.
    
    
14. 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.
    
    
15. 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.
    
    
16. The packing chromatic number of hypercubes (with Pablo Torres). Discrete Applied Mathematics, Vol. 190-191, pp. 127-140, 2015.
    
    
17. 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.
    
    
18. On the minimum sum coloring of P4-sparse graphs (with Flavia Bonomo). Graphs and Combinatorics, Vol. 30, No. 2, pp. 303-314, 2014.
    
    
19. 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.
    
    
20. 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.
    
    
21. Idomatic partitions of direct products of complete graphs. Discrete Mathematics, Vol. 310, No. 5, pp. 1118-1122, 2010.
    
    
22. Minimum Sum Edge Colorings of Multicycles (with Jean Cardinal, Vlady Ravelomanana). Discrete Applied Mathematics, Vol. 158, No. 12, pp. 1216-1223, 2010.
    
    
23. 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.
    
    
24. 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.
    
    
25. 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.
    
    
26. On the diameter of Kneser graphs (with Juan Vera). Discrete Mathematics, Vol. 305, No. 1-3, pp. 383-385, 2005.
    
    
27. On approximating the b-chromatic number (with Sylvie Corteel, Juan Vera). Discrete Applied Mathematics, Vol. 146, No. 1, pp. 618-622, 2005.
    
    
28. Revisiting Tucker's algorithm to color circular arc graphs. SIAM Journal on Computing, Vol. 32, No. 4, pp. 1067-1072, 2003.
    
    
29. 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

1. Spectral properties of stellohedra (with Ana Gargantini, Adrián Pastine, Pablo Torres). In Proc. of LAGOS’25 symposium, Procedia Computer Science 273:285-292, November 2025.
   
   
2. Computing Distances on Graph Associahedra is Fixed-parameter Tractable (with Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza). In Proc. of ICALP 2025, 63:1-63:19, LIPIcs volume 334, July 2025.
   
   
3. 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.
   
   
4. 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.
   
   
5. 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.
   
   
6. 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.
   
   
7. 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.
   
   
8. 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.
   
   
9. 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.
   
   
10. 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.
    
    
11. 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.
    
    
12. 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.
    
    
13. 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.
    
    
14. 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.
    
    
15. 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.
    
    
16. 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.
    
    
17. Some results on an extension of the line communication model (with Dominique Barth). In Proc. of ALGOTEL'99, pp. 23-27, 1999.
    
    
18. Emulation dynamique de réseaux d'interconnexion. In Proc. of RENPAR'97, pp. 135-138, 1997.

Editorial work

1. 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.
   
   
2. 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.
   
   
3. 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.
   
   
4. 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

1. Variations of the graph coloring problem : theoretical aspects and algorithms. Habilitation à diriger des recherches. Université Paris-Nord. 2009.
   
   
2. 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

1. A note on coloring powers of cycles (with Martín F. Jiménez). Technical Report, Los Andes University, Math. Dept., 2005.
   
   
2. 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: