PAPERS OF MARIO VALENCIA-PABON

Preprints submitted to journals

1. On the minimum sum coloring of P4-sparse graphs (with F. Bonomo). 2011.

Journals

1. Minimum sum set coloring of trees and line graphs of trees (with F. Bonomo, G. Duran, J. Marenco). Discrete Applied Mathematics, Vol. 159, No. 5, pp. 288-294, 2011.
2. 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.
3. Idomatic partitions of direct products of complete graphs. Discrete Mathematics, Vol. 310, No. 5, pp. 1118-1122, 2010.
4. Minimum Sum Edge Colorings of Multicycles (with J. Cardinal, V. Ravelomanana). Discrete Applied Mathematics, Vol. 158, No. 12, pp. 1216-1223, 2010.
5. On the b-coloring of cographs and P4-sparse graphs (with F. Bonomo, G. Duran, F. Maffray, J. Marenco). Graphs and Combinatorics, Vol. 25, No. 2, pp. 153-167, 2009.
6. A distributed approximation algorithm for the minimum degree minimum weight spanning trees (with C. Lavault). Journal of Parallel and Distributed Computing, Vol. 68, No. 2, pp. 200-208, 2008.
7. Independence and coloring properties of direct products of some vertex-transitive graphs (with J. Vera). Discrete Mathematics, Vol. 306, No. 18, pp. 2275-2281, 2006.
8. On the diameter of Kneser graphs (with J. Vera). Discrete Mathematics, Vol. 305, No. 1-3, pp. 383-385, 2005.
9. On approximating the b-chromatic number (with S. Corteel, J. Vera). Discrete Applied Mathematics, Vol. 146, No. 1, pp. 618-622, 2005.
10. Revisiting Tucker's algorithm to color circular arc graphs. SIAM Journal on Computing, Vol. 32, No. 4, pp. 1067-1072, 2003.
11. The permutation-path coloring problem on trees (with S. Corteel, D. Gardy, D. Barth, A. Denise). Theoretical Computer Science, Vol. 297, pp. 119-143, 2003.

In proceedings

1. On lower bounds for the b-chromatic number of connected bipartite graphs (with M. Kouider). In Proc. of LAGOS'11 symposium, Electronic Notes in Discrete Mathematics, Vol. 37, pp. 399-404, 2011.
2. Sum coloring of P4-sparse graphs (with F. Bonomo). In Proc. of LAGOS'09 symposium, Electronic Notes in Discrete Mathematics, Vol. 35, pp. 293-298, 2009.
3. Sum set coloring of some block graphs (with F. Bonomo, G. Duran, J. Marenco). In Proc. of Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 195-198, 2009.
4. Chromatic Edge Strength of Some Multigraphs (with J. Cardinal, V. Ravelomanana). In Proc. of LAGOS'07 symposium, Electronic Notes in Discrete Mathematics, Vol. 30, pp. 39-44, 2008.
5. 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.
6. On the Complexity of routing permutations on trees by arc-disjoint paths (with S. Corteel, D. Gardy, D. Barth, A. Denise). In proc. of LATIN 2000, LNCS 1776, pp. 308-317, Springer-Verlag, 2000.
7. Message scheduling on trees under a generalised line-communication model (with D. Barth). In Proc. of I-SPAN'99, pp. 10-15, IEEE CS Press, 1999.
8. Some results on an extension of the line communication model (with D. Barth). In Proc. of ALGOTEL'99, pp. 23-27, 1999.
9. Emulation dynamique de réseaux d'interconnexion. In Proc. of RENPAR'97, pp. 135-138, 1997.

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.