Keywords
teoría de graficas
coloración sobre vértices
soft graph coloring
graph theory
coloring on vertexes
How to Cite
Abstract
In this paper a Soft Graph Coloring Model is proposed, which is colored based on weights on the edges of the graph. It is shown that this model is very flexible and includes other similar problems such as Minimal, Equitable, Weak, and Robust Graph Coloring. A linear binary solution model and some test instances are also proposed.References
Burke, E.K.; Jackson, K.; Kingston, J.; Weare, R. (1997) “Automated university timetabling: the state of the art”, Comput. J. 40: 565–571.
Burke, E.K.; Petrovic, S. (2002) “Recent research directions in automated timetabling”, Eur. J. Opl. Res. 140: 266–280.
Cangalovic, M.; Schreuder, J.A.M. (1991) “Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths”, Eur. J. Opl. Res. 51: 248–258.
Carter, M.W.; Laporte, G. (1998) “Recent developments in practical course timetabling”, in: E.R. Burke & M. Carter (Eds) Practice and Theory of Automated Timetabling II, Second International Conference, PATAT’97, Toronto, Canada: 3–19.
Cowen, L.; Goddard, W.; Jesurum C.E. (1997) “Defective Coloring Revisited”, J. Graph. Theory 24(3): 205–219.
Diestel, R. (2000) Graph Theory. Springer-Verlag, New York.
Kuhn, F. (2009) “Weak graph colorings: distributed algorithms and applications”, SPAA’09, Calgary, Alberta, Canada: 138–144.
McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, A.; Di Gaspero, L.; Qu, R.; Burke E. (2009) “Setting the research agenda in automated timetabling: the Second International Timetabling Competition”, INFORMS Journal on Computing, doi: 10.1287/ijoc.1090.0320.
Meyer, W. (1973) “Equitable coloring”, American Mathematical Monthly (Mathematical Association of America) 80: 920–922, doi: 10.2307/2319405
Nandhini, M.; Kanmani, S. (2009) “A survey of simulated annealing methodology for university course timetabling”, International Journal of Recent Trends in Engineering 1: 255–257.
Ramírez, J. (2001) Extensiones del problema de coloración de gráfos. Tesis Doctoral, Universidad Complutense de Madrid, Madrid, España.
Roberts, F.S. (1991) “T-colorings of graphs: recent results and open problems´´, Discrete Math. 93: 229–245.
Wang, F.; Xu, Z. (2013) “Heuristics for robust graph coloring”, J. Heuristics 19: 529–548. doi: 10.1007/s10732-011-9180-4
Yañez, J.; Ramírez, J. (2003) “The robust coloring problem”, European Journal of Operational Research, 148(3): 546–558.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2015 Revista de Matemática: Teoría y Aplicaciones