I grafteorin är en välordnad graf en graf vars hörn kan ordnas på ett sådant sätt att den giriga färgningsalgoritmen med denna ordning optimalt färgar varje genererad subgraf i den givna grafen. Motsvarande ordning kallas perfekt . Fullständigt beställningsbara grafer utgör en underklass av perfekta grafer, och denna underklass inkluderar ackordsgrafer , jämförbarhetsgrafer och avståndsärvda grafer . Att kontrollera om en graf är helt beställningsbar är dock ett NP-komplett problem.
Den giriga färgningsalgoritmen, när den tillämpas på en given ordning av hörnen i en graf G , betraktar grafens hörn sekventiellt (enligt ordningen) och tilldelar varje vertex den första tillgängliga färgen. Olika vertexordningar kan resultera i att olika antal färger krävs. Det finns alltid en ordning som leder till en optimal färgsättning - det gäller till exempel när du beställer hörn enligt färgerna på den optimala färgen, men en sådan ordning kan råka vara svår att hitta. Välordnade grafer, per definition, är grafer för vilka det finns en ordning som är optimal för den giriga färgningsalgoritmen, inte bara för själva grafen utan också för alla dess genererade subgrafer .
Mer formellt sägs en graf G vara fullständigt beställningsbar om det finns en ordningsföljd π av hörnen i G så att varje genererad subgraf av G färgas optimalt av den giriga färgningsalgoritmen med hjälp av ordningsföljden π som genereras av undergrafens hörn . En ordningsföljd π har denna egenskap exakt när det inte finns fyra hörn a , b , c och d för vilka abcd är en genererad subgraf där a kommer före b (i ordningen) och c kommer efter d [1] [2 ] .
Identifieringen av välordnade grafer är ett NP-komplett problem [3] [2] . Det är dock lätt att kontrollera om en viss beställning uppfyller perfekt (d.v.s. uppfyller kraven för en helt beställningsbar graf). Därför är det ett NP-svårt problem att hitta en perfekt ordning på en graf, även om man vet på förhand att grafen är helt ordnad.
Alla helt beställningsbara grafer är perfekta . [1] [2]
Ackordsgrafer är helt beställningsbara. Den perfekta ordningen för ackordsgrafer kan hittas genom att vända om den perfekta undantagsordningen för grafen. Att tillämpa den giriga färgningsalgoritmen till en perfekt ordning ger alltså en effektiv färgningsalgoritm för ackordsgrafer. Jämförbarhetsgrafer är också helt beställbara, där den perfekta ordningen bestäms av den topologiska ordningen för grafens transitiva orientering [1] [2] .
En annan klass av välordnade grafer består av grafer G så att i vilken delmängd som helst av fem hörn i G har minst en av de fem hörnen ett slutet område , vilket är en delmängd av (eller lika med) de stängda områdena i den andra hörn i topp fem. På motsvarande sätt är dessa grafer där den partiella ordningen för slutna kvarter som definieras av inkluderingen av mängder har en bredd på högst 4. En cykelgraf med 5 hörn har en partiell grannskapsordning med bredd lika med fem, så fyra är den maximala bredden som ger en perfekt ordning. Liksom i fallet med ackordsgrafer (men i allmänhet inte för helt beställningsbara grafer i allmänhet), känns grafer med bredd fyra i polynomtid [4] [5] .
Konceptet mellan perfekt elimineringsordning för ackordsgrafer och perfekt ordning är begreppet semi-perfekt elimineringsordning . I det perfekta elimineringskonceptet finns det ingen 3-punktsgenererad bana där den mellersta vertexen elimineras först, och i den semi-perfekta elimineringsordningen finns det inga 4-vertexgenererade banor där en av de mittersta hörnen tas bort före de andra från de fyra. Omkastningen av en sådan ordning uppfyller alltså kraven på en perfekt ordning, så att grafer med semiperfekt elimineringsordning är helt beställbara [6] [7] . I synnerhet kan den lexikografiska bredd-först sökalgoritm som används för att hitta den perfekta exkluderingsordningen för ackordsgrafer användas för att hitta den semiperfekta exkluderingsordningen för avståndsärvda grafer , som alltså också är helt beställbara [8] .
Grafer för vilka någon ordning av hörn är perfekt är kografer , som är både ackords- och avståndsärvda grafer [9] . Eftersom kografer inte innehåller genererade banor med fyra hörn, kan de inte bryta mot kravet på att banorna ska ordnas i perfekt ordning.
Vissa andra klasser av helt beställningsbara grafer är kända [10] [6] [11] [2] [12] .