Mycielskian graph M2
Name mycielskian2
Group Mycielski
Matrix ID 2758
Num Rows 2
Num Cols 2
Nonzeros 2
Pattern Entries 2
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 M2.                                                   
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 (M2) include the following:              
 * M2 has a minimum chromatic number of 2.                              
 * M2 is triangle-free (i.e. no cycles of length 3 exist).              
 * M2 has a Hamiltonian cycle.                                          
 * M2 has a clique number of 2.                                         
 * M2 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.