On the connection between chromatic number, maximal clique and minimal degree of a graph
From MaRDI portal
Publication:1844683
DOI10.1016/0012-365X(74)90133-2zbMath0284.05106OpenAlexW2168685161WikidataQ105583523 ScholiaQ105583523MaRDI QIDQ1844683
Vera T. Sós, Paul Erdős, B. Andrasfai
Publication date: 1974
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(74)90133-2
Related Items
The clique number and the smallest \(Q\)-eigenvalue of graphs, The exact linear Turán number of the sail, Making Kr+1-free graphs r-partite, The chromatic profile of locally colourable graphs, Complete subgraphs in a multipartite graph, Cliques in Graphs With Bounded Minimum Degree, Large generalized books are \(p\)-good, Dense graphs with small clique number, Minimum Degrees for Powers of Paths and Cycles, Hypergraphs with zero chromatic threshold, Triangle-free subgraphs of random graphs, Triangle-free four-chromatic graphs, On set systems with a threshold property, A Brooks‐Type Theorem for the Bichromatic Number, Additive approximation for edge-deletion problems, Turán number of generalized triangles, Triangle-Free Graphs with High Minimal Degrees, On the local structure of oriented graphs -- a case study in flag algebras, A new class of Ramsey-Turán problems, On the local density problem for graphs of given odd-girth, On the Structure of Graphs with Given Odd Girth and Large Minimum Degree, The chromatic profile of locally bipartite graphs, Generalized Turán results for intersecting cliques, Andrásfai and Vega graphs in Ramsey–Turán theory, A geometric version of the Andrásfai-Erdős-Sós theorem, A note on independent sets in graphs with large minimum degree and small cliques, A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs, Bipartite-ness under smooth conditions, Off-diagonal book Ramsey numbers, Regular Turán numbers and some Gan–Loh–Sudakov‐type problems, Minimum degree and the graph removal lemma, Ramsey non-goodness involving books, A note on Ramsey numbers involving large books, A 2-stable family of triple systems, Triangle-free graphs with the maximum number of cycles, The minimum degree removal lemma thresholds, On the Chromatic Thresholds of Hypergraphs, Nearly bipartite graphs, Stability theorems for some Kruskal-Katona type results, On a conjecture of Erdős and Simonovits: even cycles, Semi-regular graphs of minimum independence number, Strong Turán stability, On degree sums of a triangle-free graph, Cycle-maximal triangle-free graphs, \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups, On the KŁR conjecture in random graphs, On the chromatic number of \(H\)-free graphs of large minimum degree, Rainbow neighbourhood number of graphs, On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite, The maximum edit distance from hereditary graph properties, Sparse halves in dense triangle-free graphs, Extremal non-bipartite regular graphs of girth 4, Joints in graphs, Cycles and stability, Triangles in Regular Graphs with Density Below One Half, Triangle-Free Subgraphs of Random Graphs, Strong Turán stability, Quadruple systems with independent neighborhoods, Note on robust critical graphs with large odd girth, Cycles of given length in oriented graphs, The binding number of a graph and its cliques, Books in graphs, Some sharp results on the generalized Turán numbers, A note on generalized pentagons, Sparse halves in triangle-free graphs, A stability theorem for maximal \(K_{r+1}\)-free graphs, 4-factor-criticality of vertex-transitive graphs, On the minimal degree condition of graphs implying equality of the largest \(K_r\)-free subgraphs and \((r - 1)\)-partite subgraphs, Some results on \(k\)-Turán-good graphs, A problem of Erdős on the minimum number of \(k\)-cliques, Regular Tur\'an numbers, An Extension of Mantel’s Theorem to k-Graphs, A note on stability for maximal \(F\)-free graphs, On the structure of Dense graphs with bounded clique number, Hardness of edge-modification problems, A new Turán-type theorem for cliques in graphs, Triangle-degrees in graphs and tetrahedron coverings in 3-graphs, Eigenvalues and triangles in graphs, On a valence problem in extremal graph theory, Homomorphism thresholds for odd cycles, Regular \(K_n\)-free graphs, Turán's theorem inverted, The maximum number of triangles in a \(K_4\)-free graph, Graphs of odd girth 7 with large degree, Cliques in graphs with bounded minimum degree, Odd wheels in graphs, Smallest regular graphs with girth pair \((4,2t+1)\), Exact stability for Turán’s Theorem, Note on rainbow triangles in edge-colored graphs
Cites Work
