There are various variants of graph coloring, such as when I want to compute the star chromatic number of a graph, Mathematica seems not to provide relevant functions.
Fortunately, the software ColPack offers this functionality. However, it supports the MTX format. So, the question is:
- How can I write a graph in MTX format?
And
- how can the MTX format be converted into a graph format?
Of course, I would like to perform these operations in Mathematica.
The following is an example (bcsstk01.mtx) in the directory ColPack-master/Graphs directory
of the source code of ColPack.
%%MatrixMarket matrix coordinate real symmetric
48 48 224
1 1 2.8322685185200e+06
5 1 1.0000000000000e+06
6 1 2.0833333333300e+06
7 1 -3.3333333333300e+03
11 1 1.0000000000000e+06
19 1 -2.8000000000000e+06
25 1 -2.8935185185200e+04
30 1 2.0833333333300e+06
2 2 1.6354475308600e+06
4 2 -2.0000000000000e+06
6 2 5.5555555555500e+06
8 2 -6.6666666666700e+03
10 2 -2.0000000000000e+06
20 2 -3.0864197530900e+04
24 2 5.5555555555500e+06
26 2 -1.5979166666700e+06
3 3 1.7243672839500e+06
4 3 -2.0833333333300e+06
5 3 -2.7777777777800e+06
9 3 -1.6800000000000e+06
21 3 -1.5432098765400e+04
23 3 -2.7777777777800e+06
27 3 -2.8935185185200e+04
28 3 -2.0833333333300e+06
4 4 1.0033333333300e+09
8 4 2.0000000000000e+06
10 4 4.0000000000000e+08
22 4 -3.3333333333300e+06
27 4 2.0833333333300e+06
28 4 1.0000000000000e+08
5 5 1.0675000000000e+09
7 5 -1.0000000000000e+06
11 5 2.0000000000000e+08
21 5 2.7777777777800e+06
23 5 3.3333333333300e+08
29 5 -8.3333333333300e+05
6 6 1.5353333333300e+09
12 6 -2.0000000000000e+06
20 6 -5.5555555555500e+06
24 6 6.6666666666700e+08
25 6 -2.0833333333300e+06
30 6 1.0000000000000e+08
7 7 2.8322685185200e+06
11 7 -1.0000000000000e+06
12 7 2.0833333333300e+06
13 7 -2.8000000000000e+06
31 7 -2.8935185185200e+04
36 7 2.0833333333300e+06
8 8 1.6354475308600e+06
10 8 2.0000000000000e+06
12 8 5.5555555555500e+06
14 8 -3.0864197530900e+04
18 8 5.5555555555500e+06
32 8 -1.5979166666700e+06
9 9 1.7243672839500e+06
10 9 -2.0833333333300e+06
11 9 -2.7777777777800e+06
15 9 -1.5432098765400e+04
17 9 -2.7777777777800e+06
33 9 -2.8935185185200e+04
34 9 -2.0833333333300e+06
10 10 1.0033333333300e+09
16 10 -3.3333333333300e+06
33 10 2.0833333333300e+06
34 10 1.0000000000000e+08
11 11 1.0675000000000e+09
15 11 2.7777777777800e+06
17 11 3.3333333333300e+08
35 11 -8.3333333333300e+05
12 12 1.5353333333300e+09
14 12 -5.5555555555500e+06
18 12 6.6666666666700e+08
31 12 -2.0833333333300e+06
36 12 1.0000000000000e+08
13 13 2.8360994695000e+06
17 13 -2.1492852945100e+06
18 13 2.3591618040200e+06
19 13 -3.3333333333300e+03
23 13 -1.0000000000000e+06
37 13 -2.8935185185200e+04
42 13 2.0833333333300e+06
43 13 -3.8309509817100e+03
47 13 -1.1492852945100e+06
48 13 2.7582847068300e+05
14 14 1.7674107444600e+06
15 14 5.1792213181600e+05
16 14 4.2985705890200e+06
18 14 -5.5555555555500e+06
20 14 -6.6666666666700e+03
22 14 2.0000000000000e+06
38 14 -1.5979166666700e+06
44 14 -1.3196321359900e+05
45 14 -5.1792213181600e+05
46 14 2.2985705890200e+06
15 15 3.8900380684800e+06
16 15 -2.6349902747000e+06
17 15 2.7777777777800e+06
21 15 -1.6800000000000e+06
39 15 -2.8935185185200e+04
40 15 -2.0833333333300e+06
44 15 -5.1792213181600e+05
45 15 -2.1656707845300e+06
46 15 -5.5165694136700e+05
16 16 1.9757206353100e+09
20 16 -2.0000000000000e+06
22 16 4.0000000000000e+08
39 16 2.0833333333300e+06
40 16 1.0000000000000e+08
44 16 -2.2985705890200e+06
45 16 5.5165694136600e+05
46 16 4.8619365099000e+08
17 17 1.5273465154700e+09
18 17 -1.0977973133200e+08
19 17 1.0000000000000e+06
23 17 2.0000000000000e+08
41 17 -8.3333333333300e+05
43 17 1.1492852945100e+06
47 17 2.2972466123600e+08
48 17 -5.5717351077900e+07
18 18 1.5641114371100e+09
24 18 -2.0000000000000e+06
37 18 -2.0833333333300e+06
42 18 1.0000000000000e+08
43 18 -2.7582847068300e+05
47 18 -5.5717351077900e+07
48 18 1.0941196003800e+07
19 19 2.8322685185200e+06
23 19 1.0000000000000e+06
24 19 2.0833333333300e+06
43 19 -2.8935185185200e+04
48 19 2.0833333333300e+06
20 20 1.6354475308600e+06
22 20 -2.0000000000000e+06
24 20 -5.5555555555500e+06
44 20 -1.5979166666700e+06
21 21 1.7243672839500e+06
22 21 -2.0833333333300e+06
23 21 2.7777777777800e+06
45 21 -2.8935185185200e+04
46 21 -2.0833333333300e+06
22 22 1.0033333333300e+09
45 22 2.0833333333300e+06
46 22 1.0000000000000e+08
23 23 1.0675000000000e+09
47 23 -8.3333333333300e+05
24 24 1.5353333333300e+09
43 24 -2.0833333333300e+06
48 24 1.0000000000000e+08
25 25 6.0879629629600e+04
29 25 1.2500000000000e+06
30 25 4.1666666666700e+05
31 25 -4.1666666666700e+03
35 25 1.2500000000000e+06
26 26 3.3729166666700e+06
28 26 -2.5000000000000e+06
32 26 -8.3333333333300e+03
34 26 -2.5000000000000e+06
27 27 2.4117129629600e+06
28 27 -4.1666666666700e+05
33 27 -2.3550000000000e+06
28 28 1.5000000000000e+09
32 28 2.5000000000000e+06
34 28 5.0000000000000e+08
29 29 5.0183333333300e+08
31 29 -1.2500000000000e+06
35 29 2.5000000000000e+08
30 30 5.0250000000000e+08
36 30 -2.5000000000000e+06
31 31 3.9858796296300e+06
35 31 -1.2500000000000e+06
36 31 4.1666666666700e+05
37 31 -3.9250000000000e+06
32 32 3.4114969135800e+06
34 32 2.5000000000000e+06
36 32 6.9444444444400e+06
38 32 -3.8580246913600e+04
42 32 6.9444444444500e+06
33 33 2.4310030864200e+06
34 33 -4.1666666666700e+05
35 33 -3.4722222222200e+06
39 33 -1.9290123456800e+04
41 33 -3.4722222222200e+06
34 34 1.5041666666700e+09
40 34 -4.1666666666700e+06
35 35 1.3351666666700e+09
39 35 3.4722222222200e+06
41 35 4.1666666666700e+08
36 36 2.1691666666700e+09
38 36 -6.9444444444400e+06
42 36 8.3333333333300e+08
37 37 3.9858796296300e+06
41 37 -1.2500000000000e+06
42 37 4.1666666666700e+05
43 37 -4.1666666666700e+03
47 37 -1.2500000000000e+06
38 38 3.4114969135800e+06
40 38 2.5000000000000e+06
42 38 -6.9444444444500e+06
44 38 -8.3333333333300e+03
46 38 2.5000000000000e+06
39 39 2.4310030864200e+06
40 39 -4.1666666666700e+05
41 39 3.4722222222200e+06
45 39 -2.3550000000000e+06
40 40 1.5041666666700e+09
44 40 -2.5000000000000e+06
46 40 5.0000000000000e+08
41 41 1.3351666666700e+09
43 41 1.2500000000000e+06
47 41 2.5000000000000e+08
42 42 2.1691666666700e+09
48 42 -2.5000000000000e+06
43 43 6.4710580611300e+04
47 43 2.3992852945100e+06
48 43 1.4083819598400e+05
44 44 3.5048798802700e+06
45 44 5.1792213181600e+05
46 44 -4.7985705890200e+06
45 45 4.5773837474900e+06
46 45 1.3499027470000e+05
46 46 2.4723873019800e+09
47 47 9.6167984880400e+08
48 47 -1.0977973133200e+08
48 48 5.3127810377500e+08
./ColPack -f ../../Graphs/bcsstk01.mtx -m STAR
Out: 11
But I do not know what the graph in the example is. I don't understand what the very long decimal numbers (like 2.8322685185200e+06
) in the third column in the MTX-file. Will it affect the imformation of the entire graph?
On the contrary, I would like to compute the star chromatic number of the graph below, and I also don't know how to convert it into the MTX format like the above.
G = GridGraph[{2, 2, 2, 3}, VertexLabels -> "Name"]
s = Import["~\\ColPack-master\\Graphs\ \\bcsstk01.mtx", "Graphics"]
$\endgroup$2.8322685185200e+06
) in the third column in the MTX-matrix. $\endgroup$