Mycielskian graph M17
Name mycielskian17
Group Mycielski
Matrix ID 2773
Num Rows 98,303
Num Cols 98,303
Nonzeros 100,245,742
Pattern Entries 100,245,742
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
Mycielskian graph M17.                                                  
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 (M17) include the following:             
 * M17 has a minimum chromatic number of 17.                            
 * M17 is triangle-free (i.e. no cycles of length 3 exist).             
 * M17 has a Hamiltonian cycle.                                         
 * M17 has a clique number of 2.                                        
 * M17 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 
    Mycielski, J., 1955. Sur le coloriage des graphes. Colloq. Math.,   
    3: 161-162.