A358316 Number of edge-4-critical graphs on n unlabeled vertices.

1, 0, 1, 2, 5, 21, 150, 1221, 14581, 207969, 3567180

Offset

4,4

Comments

An undirected simple graph G is edge-4-critical if it is connected, is not (vertex) 3-colorable, and G-e is 3-colorable for every edge e.

Toft's paper has drawings of the graphs with at most 9 vertices. - Allan Bickle, Oct 15 2025

Links

Table of n, a(n) for n=4..14.

Brendan McKay, Graphs.

Bjarne Toft, On critical subgraphs of colour-critical graphs, Discrete Math. 7 3-4, (1974), 377-392.

Example

For n=4, the only 4-critical graph is K_4.
For n=6, the only 4-critical graph is the wheel W_6.
For n=7, the two 4-critical graphs are the Moser spindle and the Mycelskian of K_3.

Crossrefs

Sequence in context: A383938 A144271 A193189 * A391072 A176527 A117261

Adjacent sequences: A358313 A358314 A358315 * A358317 A358318 A358319

Keyword

nonn,more

Author

Brendan McKay, Nov 08 2022

Extensions

a(14) added by Allan Bickle, Oct 15 2025

Status

approved