A345246
Number of 2-connected unlabeled simple graphs with no triangles.
Original entry on oeis.org
1, 2, 6, 16, 78, 415, 3374, 35860, 524386, 10193061, 263036202, 8948113645, 400280198048
Offset: 4
For n=4 the only example is a 4-cycle.
Cf.
A002218 all 2-connected graphs.
Cf.
A024607 all connected triangle-free graphs.
A352212
Largest number of maximal triangle-free node-induced subgraphs of an n-node graph.
Original entry on oeis.org
1, 1, 3, 6, 10, 15, 21, 36, 60
Offset: 1
For 2 <= n <= 7, a(n) = binomial(n,2) = A000217(n-1) and the complete graph is optimal (it is the unique optimal graph for 3 <= n <= 7), but a(8) = 36 > binomial(8,2), with the optimal graphs being K_4 + K_4, with up to 4 additional node-disjoint edges. For n = 9 the optimal graphs are K_4 + K_5 with up to 4 additional node-disjoint edges.
For a list of related sequences, see cross-references in
A342211.
A243275
Number of graphs with n nodes that are Hamiltonian and triangle-free.
Original entry on oeis.org
1, 0, 0, 1, 1, 4, 5, 35, 130, 1293, 13529, 232852, 5009335, 147950020
Offset: 1
Cf.
A003216 (Hamiltonian graphs),
A024607 (connected triangle-free graphs).
a(11)-a(14) added using tinygraph by
Falk Hüffner, Aug 15 2017
A243326
Number of simple connected graphs with n nodes that are triangle-free and not integral.
Original entry on oeis.org
0, 0, 1, 2, 5, 16, 58, 264, 1380, 9818
Offset: 1
A243334
Number of simple connected graphs with n nodes that are distance regular and triangle-free.
Original entry on oeis.org
1, 1, 0, 1, 1, 2, 1, 3, 1, 4, 1, 3, 1, 5, 1, 5, 1, 4
Offset: 1
Cf.
A241814 (distance regular graphs),
A024607 (triangle-free graphs).
A243335
Number of simple connected graphs with n nodes that are Eulerian and triangle-free.
Original entry on oeis.org
1, 0, 0, 1, 1, 2, 3, 8, 19, 62, 229, 1192, 8147, 80182, 1106086
Offset: 1
a(11)-a(15) added using tinygraph by
Falk Hüffner, Jan 15 2016
A292528
Minimal number of vertices in a triangle-free graph with chromatic number n.
Original entry on oeis.org
1, 2, 5, 11, 22
Offset: 1
The unique graph for a(1) = 1 is a lone vertex.
The unique graph for a(2) = 2 is two vertices connected by an edge.
The unique graph for a(3) = 5 is the cycle graph C_5 (the pentagon).
The unique graph for a(4) = 11 is the Grötzsch graph.
There are 80 graphs for a(5) = 22, see Jensen & Royle reference and the Royle link.
- F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. (1969), p. 149.
- V. Chvátal, The minimality of the Mycielski graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Ed. by R. A. Bari and F. Harary, pp. 243-246. Lecture Notes in Mathematics 406, Springer, Berlin, 1974.
- Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs (2017)
- House of Graphs, Triangle-free k-chromatic graphs
- T. Jensen and G. F. Royle, Small graphs with chromatic number 5, A computer search, Journal of Graph Theory 19 (1995), pp. 107-116.
- J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), pp. 161-162.
- Gordon Royle, Smallest triangle-free graph with chromatic number 5 (2018)
Comments