scientific article; zbMATH DE number 3251276

From MaRDI portal
Publication:5536129





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\).




Cited in
(28)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5536129)