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