×

On graphs without 6-cycles and related Ramsey numbers. (English) Zbl 0789.05070

Summary: Let \(t_ 6(n)\) denote the maximum number of edges in a graph with \(n\) vertices and no 6-cycle \(C_ 6\). The values of \(t_ 6(n)\), \(6 \leq n \leq 21\), are found by computer. The corresponding extremal graphs can be determined at the same time, and sufficient information on \(C_ 6\)-free 3-colourings is obtained to show that the Ramsey number \(r_ 3(C_ 6)\) is equal to 12.

MSC:

05C55 Generalized Ramsey theory
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite