On the minimal number of edges in color-critical graphs (Q1272188)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the minimal number of edges in color-critical graphs
scientific article

    Statements

    On the minimal number of edges in color-critical graphs (English)
    0 references
    24 November 1998
    0 references
    Given a critical \(k\)-chromatic graph with \(e\) edges, \(n\) vertices, and no \((s+1)\)-clique (\(3\leq s<k\)), the inequalities \(e\geq ({k\over 2} -{k-2 \over{2(2k-s-3)}})n\) (for \(s\leq {2k \over 3}\)) and \(e\geq ({k\over 2} -{{(k-2)s\over {2(2ks-2k-s^2)}}})n\) (for \(s\geq {2k \over 3}\)) hold. For \(s=k-1\) this improves the earlier estimate \(e\geq ({k-1 \over 2}+{k-3 \over {2(k^2-3)}})n\) of Gallai.
    0 references
    extremal graph theory
    0 references
    chromatic critical graphs
    0 references

    Identifiers