TNN04-L105R Comments on the 1993 DIMACS Graph Coloring Challenge"and "Energy Function-Based Approaches to Graph Coloring" Jing Liu,Weicai Zhong,and Licheng Jiao,Senior Member,IEEE The problems in the first class are right,whereas those in the Abstract-Since all graphs in the 1993 DIMACS graph coloring two other classes may cause confusion.Table I gives the class challenge are undirected,each edge should be only counted once. of each problem.For the problems in the second class,the But in some files each edge is counted once,whereas in others each number of edges in the problem line should be divided by 2. edge is counted twice.So a systematical check on the DIMACS challenge is made to eliminate the inconsistencies.Besides,the and the edge lines should be let as they are.For the problems in experimental results of [2]counted each violated edges twice and the third class,the number of edges in the problem line should neglected the inconsistencies in the DIMACS challenge.So the be also divided by 2,and one of the two edge lines correct experimental results of 2 are also given. corresponding to the same edge should be deleted. For the files in the compressed format,the problem lines are Index Terms-Graph coloring,DIMACS challenge the same as those of the corresponding files in the DIMACS standard format,and the lower triangular part of the vertex-vertex adjacency matrix of the graph is given.So their I.INCONSISTENCIES IN THE 1993 DIMACS GRAPH COLORING inconsistencies can be corrected according to the above CHALLENGE paragraph. THE 1993 DIMACS graph coloring challenge [1]has been widely used in testing various new approaches for graph coloring problems.Since all graphs in the DIMACS challenge II.INCONSISTENT EXPERIMENTAL RESULTS OF [2] are undirected,each edge should be only counted once.But in The experiments of [2]used some graphs from the 1993 some files each edge is counted once,whereas in others each DIMACS graph coloring challenge.The authors of [2] edge is counted twice.These inconsistencies have affected neglected the inconsistencies pointed out in Section I,and many experimental results,and made many comparisons unfair. counted each violated edge twice in the coloring results.As a In what follows,a systematical check on the DIMACS result,the experimental results for the spanning subgraph challenge is made to eliminate the inconsistencies. Presently,the DIMACS challenge has 79 problems.They are k-coloring(SSC)problems in Table I of [2]are inconsistent.It brings difficulties for the other researches that want to make a given in two formats,namely,the DIMACS standard format comparison with [21.The correct results are given in Table II. and the compressed format.A translator is also given to go between the two formats.Each file in the DIMACS standard format has a problem line beginning with the letter p'.This ACKNOWLEDGMENT line gives the number of nodes and the number of edges of the graph.Following the problem line,each edge is given by a line The authors thank Andrea Di Blas,the first author of [2],for beginning with the letter 'e'.The inconsistencies lie between confirming both facts and for related discussions. the problem line and the edge lines.According to the current cases,the 79 problems can be divided into 3 classes: 1)The problem line counts each edge once,and each edge REFERENCES forms one edge line; [1]Website..[Online].Available:http://dimacs.rutgers.edu and 2)The problem line counts each edge twice,and each edge http://mat.esia.cmu.edu/COLOR/color.html [2]A.D.Blas,A.Jagota,and R.Hughey,"Energy Function-Based forms one edge line: Approaches to Graph Coloring,"IEEE Trans.Neural Networks,vol.13, 3)The problem line counts each edge twice,and each edge n0.1,Pp.81-91,2002. forms two edge lines; Manuscript received March 27,2004. The authors are with the Institute of Intelligent Information Processing, Xidian University,Xi'an,710071,China Weicai Zhong,corresponding author,phone:0086-029-88202661;fax: 0086-029-88201023;e-mail:neouma@mail.xidian.edu.cn.TNN04-L105R 1 Abstract—Since all graphs in the 1993 DIMACS graph coloring challenge are undirected, each edge should be only counted once. But in some files each edge is counted once, whereas in others each edge is counted twice. So a systematical check on the DIMACS challenge is made to eliminate the inconsistencies. Besides, the experimental results of [2] counted each violated edges twice and neglected the inconsistencies in the DIMACS challenge. So the correct experimental results of [2] are also given. Index Terms—Graph coloring, DIMACS challenge I. INCONSISTENCIES IN THE 1993 DIMACS GRAPH COLORING CHALLENGE HE 1993 DIMACS graph coloring challenge [1] has been widely used in testing various new approaches for graph coloring problems. Since all graphs in the DIMACS challenge are undirected, each edge should be only counted once. But in some files each edge is counted once, whereas in others each edge is counted twice. These inconsistencies have affected many experimental results, and made many comparisons unfair. In what follows, a systematical check on the DIMACS challenge is made to eliminate the inconsistencies. Presently, the DIMACS challenge has 79 problems. They are given in two formats, namely, the DIMACS standard format and the compressed format. A translator is also given to go between the two formats. Each file in the DIMACS standard format has a problem line beginning with the letter ‘p’. This line gives the number of nodes and the number of edges of the graph. Following the problem line, each edge is given by a line beginning with the letter ‘e’. The inconsistencies lie between the problem line and the edge lines. According to the current cases, the 79 problems can be divided into 3 classes: 1) The problem line counts each edge once, and each edge forms one edge line; 2) The problem line counts each edge twice, and each edge forms one edge line; 3) The problem line counts each edge twice, and each edge forms two edge lines; Manuscript received March 27, 2004. The authors are with the Institute of Intelligent Information Processing, Xidian University, Xi’an, 710071, China Weicai Zhong, corresponding author, phone: 0086-029-88202661; fax: 0086-029-88201023; e-mail: neouma@mail.xidian.edu.cn. The problems in the first class are right, whereas those in the two other classes may cause confusion. Table I gives the class of each problem. For the problems in the second class, the number of edges in the problem line should be divided by 2, and the edge lines should be let as they are. For the problems in the third class, the number of edges in the problem line should be also divided by 2, and one of the two edge lines corresponding to the same edge should be deleted. For the files in the compressed format, the problem lines are the same as those of the corresponding files in the DIMACS standard format, and the lower triangular part of the vertex-vertex adjacency matrix of the graph is given. So their inconsistencies can be corrected according to the above paragraph. II. INCONSISTENT EXPERIMENTAL RESULTS OF [2] The experiments of [2] used some graphs from the 1993 DIMACS graph coloring challenge. The authors of [2] neglected the inconsistencies pointed out in Section I, and counted each violated edge twice in the coloring results. As a result, the experimental results for the spanning subgraph k-coloring (SSC) problems in Table I of [2] are inconsistent. It brings difficulties for the other researches that want to make a comparison with [2]. The correct results are given in Table II. ACKNOWLEDGMENT The authors thank Andrea Di Blas, the first author of [2], for confirming both facts and for related discussions. REFERENCES [1] Website.. [Online]. Available: http://dimacs.rutgers.edu and http://mat.gsia.cmu.edu/COLOR/color.html [2] A. D. Blas, A. Jagota, and R. Hughey, “Energy Function-Based Approaches to Graph Coloring,” IEEE Trans. Neural Networks, vol. 13, no. 1, pp.81-91, 2002. Comments on “the 1993 DIMACS Graph Coloring Challenge” and “Energy Function-Based Approaches to Graph Coloring” Jing Liu, Weicai Zhong, and Licheng Jiao, Senior Member, IEEE T