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 Kind Date Download File
2758 mycielskian2 Mycielski 2 2 2 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2759 mycielskian3 Mycielski 5 5 10 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2760 mycielskian4 Mycielski 11 11 40 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2761 mycielskian5 Mycielski 23 23 142 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2762 mycielskian6 Mycielski 47 47 472 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2763 mycielskian7 Mycielski 95 95 1,510 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2764 mycielskian8 Mycielski 191 191 4,720 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2765 mycielskian9 Mycielski 383 383 14,542 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2766 mycielskian10 Mycielski 767 767 44,392 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2767 mycielskian11 Mycielski 1,535 1,535 134,710 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2768 mycielskian12 Mycielski 3,071 3,071 407,200 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2769 mycielskian13 Mycielski 6,143 6,143 1,227,742 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2770 mycielskian14 Mycielski 12,287 12,287 3,695,512 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2771 mycielskian15 Mycielski 24,575 24,575 11,111,110 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2772 mycielskian16 Mycielski 49,151 49,151 33,382,480 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2773 mycielskian17 Mycielski 98,303 98,303 100,245,742 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2774 mycielskian18 Mycielski 196,607 196,607 300,933,832 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2775 mycielskian19 Mycielski 393,215 393,215 903,194,710 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market
2776 mycielskian20 Mycielski 786,431 786,431 2,710,370,560 Undirected Graph 2018 MATLAB Rutherford Boeing Matrix Market