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
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 (89)
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
This page was built for publication: On the connection between chromatic number, maximal clique and minimal degree of a graph
