scientific article; zbMATH DE number 3251276
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\).
- scientific article; zbMATH DE number 773170
- scientific article; zbMATH DE number 4099332
- A note on the chromatic number of a graph
- Note on k-chromatic graphs
- scientific article; zbMATH DE number 3245178
- scientific article; zbMATH DE number 3851122
- scientific article; zbMATH DE number 4035863
- A note on total chromatic numbers of graphs
- On chromaticity of graphs
- scientific article; zbMATH DE number 742642
- On the existence of two non-neighboring subgraphs in a graph
- The average size of an independent set in graphs with a given chromatic number
- On complete subgraphs of r-chromatic graphs
- Chromatic partitions of a graph
- Graph coloring and Graham's greatest common divisor problem
- Graph imperfection. II
- Inverting the Turán problem with chromatic number
- Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
- Almost all graphs with high girth and suitable density have high chromatic number
- scientific article; zbMATH DE number 3882454 (Why is no real title available?)
- Graph Theory and Probability
- scientific article; zbMATH DE number 3914342 (Why is no real title available?)
- scientific article; zbMATH DE number 4108789 (Why is no real title available?)
- On circuits and subgraphs of chromatic graphs
- A lower bound for the chromatic capacity in terms of the chromatic number of a graph
- scientific article; zbMATH DE number 3520447 (Why is no real title available?)
- scientific article; zbMATH DE number 1052839 (Why is no real title available?)
- scientific article; zbMATH DE number 6986950 (Why is no real title available?)
- Improved approximations of independent sets in bounded-degree graphs
- Approximating maximum independent sets by excluding subgraphs
- The -Ramsey problem for triangle-free graphs
- Some Conjectures and Questions in Chromatic Topological Graph Theory
- scientific article; zbMATH DE number 3308988 (Why is no real title available?)
- Extended Keller graph and its properties
- Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
- Coloring graphs from random lists
- The chromatic gap and its extremes
- On coloring graphs with locally small chromatic number
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)