

A119414


Number of trianglefree graphs g on n nodes for which the chromatic number chi(g) equals r(g)=ceil((Delta(g)+1+omega(g))/2).


0



0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 21, 826, 39889
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,12


COMMENTS

Here Delta(g)=maximum node degree of g and omega(g)=clique number of g (=2 for trianglefree graphs). r(g) is conjectured by Reed to be an upper bound for chi(g) for all graphs.
The sequence is of interest as a measure of how frequently the bound is attained. For example, for n=14 there are 467871369 trianglefree graphs.


REFERENCES

B. Reed, omega, Delta and chi, J Graph Theory 27, 177212 (1998).


LINKS

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


CROSSREFS

Sequence in context: A012645 A220069 A028469 * A012819 A295038 A295529
Adjacent sequences: A119411 A119412 A119413 * A119415 A119416 A119417


KEYWORD

nonn


AUTHOR

Keith Briggs (keith.briggs(AT)bt.com), Jul 26 2006


STATUS

approved



