Mycielski/mycielskian14
Mycielskian graph M14
| Name | mycielskian14 | 
|---|---|
| Group | Mycielski | 
| Matrix ID | 2770 | 
| Num Rows | 12,287 | 
| Num Cols | 12,287 | 
| Nonzeros | 3,695,512 | 
| Pattern Entries | 3,695,512 | 
| Kind | Undirected Graph | 
| Symmetric | Yes | 
| Date | 2018 | 
| Author | J. Mycielski | 
| Editor | S. Kolodziej | 
| Download | MATLAB Rutherford Boeing Matrix Market | 
|---|---|
| Notes | Mycielskian graph M14.                                                  
                                                                        
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 (M14) include the following:             
                                                                        
 * M14 has a minimum chromatic number of 14.                            
 * M14 is triangle-free (i.e. no cycles of length 3 exist).             
 * M14 has a Hamiltonian cycle.                                         
 * M14 has a clique number of 2.                                        
 * M14 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. | 
