Kritisk graf

Ej att förväxla med Critical path-metoden i projektledning.

Till vänster uppe en vertexkritisk graf med kromatiskt nummer 6; sedan alla N-1 subgrafer med kromatisk nummer 5.

I grafteorin är en kritisk graf en oriktad graf vars alla subgrafer har ett mindre kromatiskt tal . I en sådan graf är varje vertex eller kant ett kritiskt element , i den meningen att radering av den skulle minska antalet färger som behövs i en graffärgning av den givna grafen. Minskningen av antalet färger kan inte vara mer än en.

Variationer

En $k$ -kritisk graf är en kritisk graf med kromatiskt tal $k$ . En graf $G$ med kromatiskt tal $k$ är $k$ -vertexkritisk om var och en av dess hörn är ett kritiskt element. Kritiska grafer är de minimala medlemmarna när det gäller kromatiskt antal, vilket är ett mycket viktigt mått inom grafteorin.

Några egenskaper hos en $k$ -kritisk graf $G$ med $n$ hörn och $m$ kanter:

• $G$ har bara en komponent .
• $G$ är finit (detta är de Bruijn–Erdős sats ).
• Minsta graden $\delta (G)$ följer olikheten $\delta (G)\geq k-1$ . Det vill säga att varje vertex ligger intill åtminstone $k-1$ andra. Ännu starkare är $G$$(k-1)$ - kantansluten .
• Om $G$ är en vanlig graf med graden $k-1$ , vilket betyder att varje vertex ligger intill exakt $k-1$ andra, då $G$ är antingen hela grafen $K_{k}$ med $n=k$ hörn, eller en udda cykelgraf . Detta är Brooks teorem .
• $2m\geq (k-1)n+k-3$ .
• $2m\geq (k-1)n+\lgolv (k-3)/(k^{2 }-3)\rvåning n$ .
• Antingen kan $G$ delas upp i två mindre kritiska grafer, med en kant mellan varje par av hörn som inkluderar en vertex från var och en av de två subgraferna, eller så har $G$ minst ${ \displaystyle 2k-1}$ hörn. Mer starkt, antingen $G$ har en nedbrytning av denna typ, eller för varje vertex $v$ av $G$ finns det en $k$ -färgning där ${\ displaystyle v}$ är det enda hörnet i dess färg och varannan färgklass har minst två hörn.

Graf $G$ är vertexkritisk om och endast om det för varje vertex $v$ finns en optimal korrekt färgning där $v$ är en enkelfärgsklass.

Som Hajós (1961) visade, kan varje $k$ -kritisk graf bildas från en komplett graf $K_{k}$ genom att kombinera Hajós-konstruktionen med en operation som identifierar två icke-angränsande hörn. De grafer som bildas på detta sätt kräver alltid $k$ färger i valfri färg.

En dubbelkritisk graf är en sammankopplad graf där radering av valfritt par av angränsande hörn minskar det kromatiska talet med två. Det är ett öppet problem att avgöra om $K_{k}$ är den enda dubbelkritiska $k$ -kromatiska grafen.

Se även

• Faktorkritisk graf

Vidare läsning

•   Jensen, TR; Toft, B. (1995), Graph coloring problems , New York: Wiley-Interscience, ISBN 0-471-02865-7
• Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6 augusti 2009), "On list critical graphs", Discrete Mathematics , Elsevier, 309 (15): 4931–4941, doi : 10.1016/j.disc.2008.05.021