## Group Mycielski

Group Description ```Mycielski graph adjacency matrices matrices/Mycielski/README. Scott Kolodziej, June 27, 2018. The Mycielskian graph sequence generates graphs that are triangle-free and with a known chromatic number (i.e. the minimum number of colors required to color the vertices of the graph). The sequence starts with a 2 vertex, 1 edge graph (denoted M2) and repeatedly generates subsequent graphs by applying the Mycielskian operation. In MATLAB, the (sparse) Mycielskian operation can be written as follows: function M_new = mycielski(M) [n,~] = size(M); m = nnz(M); M_new = sparse([], [], [], 2*n+1, 2*n+1, 3*m+n); M_new(1:n, 1:n) = M; M_new((n+1):2*n, :) = sparse([M sparse(n,n) ones(n,1)]); M_new(:, (n+1):2*n) = sparse([M; sparse(n,n); ones(1,n)]); end More abstractly, the structure of the Mycielskian operation can be represented by the block matrix below: n n 1 _____ _____ _ | | | | n | M | M |0| |_____|_____|_| M_new = | | | | n | M | 0 |1| |_____|_____|_| 1 | 0 | 1 |0| ------------- Known properties of the Mycielskian operation include the following: * If a graph has a minimum chromatic number k, the Mycielskian of that graph has a minimum chromatic number of k + 1. * If a graph is triangle-free (i.e. no cycles of length 3 exist), so is the Mycielskian of that graph. * If a graph has a Hamiltonian cycle, so does the Mycielskian of that graph. * If a graph is factor-critical, so is the Mycielskian of that graph, meaning that every subgraph of |V|-1 vertices has a perfect matching. Mycielski graphs were first described by Jan Mycielski in the following publication: Mycielski, J., 1955. Sur le coloriage des graphes. Colloq. Math., 3: 161-162. --------------------------------------------------------------------------------```
Displaying all 19 collection matrices
Id Name Group Rows Cols Nonzeros
2758 mycielskian2 Mycielski 2 2 2
2759 mycielskian3 Mycielski 5 5 10
2760 mycielskian4 Mycielski 11 11 40
2761 mycielskian5 Mycielski 23 23 142
2762 mycielskian6 Mycielski 47 47 472
2763 mycielskian7 Mycielski 95 95 1,510
2764 mycielskian8 Mycielski 191 191 4,720
2765 mycielskian9 Mycielski 383 383 14,542
2766 mycielskian10 Mycielski 767 767 44,392
2767 mycielskian11 Mycielski 1,535 1,535 134,710
2768 mycielskian12 Mycielski 3,071 3,071 407,200
2769 mycielskian13 Mycielski 6,143 6,143 1,227,742
2770 mycielskian14 Mycielski 12,287 12,287 3,695,512
2771 mycielskian15 Mycielski 24,575 24,575 11,111,110
2772 mycielskian16 Mycielski 49,151 49,151 33,382,480
2773 mycielskian17 Mycielski 98,303 98,303 100,245,742
2774 mycielskian18 Mycielski 196,607 196,607 300,933,832
2775 mycielskian19 Mycielski 393,215 393,215 903,194,710
2776 mycielskian20 Mycielski 786,431 786,431 2,710,370,560