Mycielski/mycielskian20

Mycielskian graph M20
Name mycielskian20
Group Mycielski
Matrix ID 2776
Num Rows 786,431
Num Cols 786,431
Nonzeros 2,710,370,560
Pattern Entries 2,710,370,560
Kind Undirected Graph
Symmetric Yes
Date 2018
Author J. Mycielski
Editor S. Kolodziej
Structural Rank
Structural Rank Full
Num Dmperm Blocks
Strongly Connect Components 1
Num Explicit Zeros 0
Pattern Symmetry 100%
Numeric Symmetry 100%
Cholesky Candidate no
Positive Definite no
Type binary
Download MATLAB Rutherford Boeing Matrix Market
Notes
Mycielskian graph M20.                                                  
                                                                        
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).                           
                                                                        
Known properties of this graph (M20) include the following:             
                                                                        
 * M20 has a minimum chromatic number of 20.                            
 * M20 is triangle-free (i.e. no cycles of length 3 exist).             
 * M20 has a Hamiltonian cycle.                                         
 * M20 has a clique number of 2.                                        
 * M20 is factor-critical, meaning 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.