No label defined (Q5536129)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3251276
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3251276

      Statements

      1967
      0 references
      topology
      0 references
      0 references
      A graph \(G\) is said to have chromatic number \(k\) if its vertices can be partioned into \(k\) classes so that two vertices in the same class are not joined by an edge and such a partitioning into \(k-1\) classes is not possible. The chromatic number of the graph \(G\) is denoted by \(H(G)\). A graph is called complete if each pair of vertices of the graph are joined by an edge. The number of vertices in the largest complete graphs which are subgraphs of the graph \(G\) is denoted by \(K(G)\), \(G_n\) always denotes a graph with exactly \(n\) vertices. It is shown that there exist strictly positive constants \(c\) and \(c'\) such that for every positive integer \(n\) there exists a graph \(G_n\) for which \(H(G_n)/K (G_n)>cn(\log n)^{-2}\) and for every \(G_n H(G_n)/K(G_n)<cn(\log n)^{-2}\). By the methods of this paper it could in fact be proved that \[ \liminf_{n \to \infty} \left(\max_{G_n} {H(G_n) \over K(G_n)} / {n \over (\log n)^2} \right) \geq {(\log 2)^2 \over 4} \text{ and } \limsup_{n \to \infty} \left(\max_{G_n} {H(G_n) \over K(G_n)} / {n \over (\log n)^2} \right) \leq (\log 2)^2. \] The author conjectures that \[ \lim_{n \to \infty} \left(\max_{G_n} {H(G_n) \over K(G_n)} / {n \over (\log n)^2} \right ) \] exists. In the last part of the paper the following interesting problems are stated: \(G(n;m)\) denotes a graph with \(n\) vertices and \(m\) edges. To determine the smallest integer \(f(l,k)\) for which there exists a graph \(G\) having \(f(l,k)\) edges and satisfying \(K(G) \leq l, H(G)=k\). It is conjectured that \(\lim_{k \to \infty} {f(2,k) \over k^3} = C < \infty\). A set of vertices of a graph \(G\) is called independent if no two of them are joined. \(I(G)\) denotes the greatest integer for which there is a set of \(I(G)\) indepenent vertices in \(G\). To determine \(g(n;k,l)\), the smallest integer for which there exists a \(G(n;g(n;k,l)\) satisfying \(I(G(n;g(n;k,l))) = I\), \(K(G(n;g(n;k,l))) = k\).
      0 references

      Identifiers