χ -avgränsad

I grafteorin är en $\chi$ -avgränsad familj ${\mathcal {F}}$ av grafer en för vilken det finns någon funktion $c$ så att för varje heltal $t$ graferna i ${\mathcal {F}}$ med $t=\omega (G)$ ( klicknummer ) kan färgas med högst $c(t)$ färger. Detta koncept och dess notation formulerades av András Gyárfás . Användningen av den grekiska bokstaven chi i termen $\chi$ -begränsad är baserad på det faktum att det kromatiska talet för en graf $G$ vanligtvis betecknas $\chi ( G)$ .

Icke-trivialitet

Det är inte sant att familjen av alla grafer är $\chi$ -avgränsad. Som Zykov (1949) och Mycielski (1955) visade finns det triangelfria grafer med godtyckligt stora kromatiska tal, så för dessa grafer är det inte möjligt att definiera ett ändligt värde på $c(2)$ . Således $\chi$ -avgränsning ett icke-trivialt begrepp, sant för vissa graffamiljer och falskt för andra.

Specifika klasser

Varje klass av grafer av begränsat kromatiskt tal är (trivialt) $\chi$ -begränsat, med $c(t)$ lika med gränsen på det kromatiska talet. Detta inkluderar till exempel de plana graferna , de tvådelade graferna och graferna för gränsad degeneration . Komplementärt är graferna där oberoendetalet är begränsat också $\chi$ -begränsade, eftersom Ramseys sats antyder att de har stora klickar.

Vizings teorem kan tolkas som att linjegraferna är $\chi$ -avgränsade, med $c(t)=t+1$ . De klofria graferna är mer generellt också $\chi$ -avgränsade med $c(t)\leq t^{2}$ . Detta kan ses genom att använda Ramseys teorem för att visa att, i dessa grafer, måste en vertex med många grannar vara en del av en stor klick. Denna gräns är nästan snäv i värsta fall, men sammankopplade klofria grafer som inkluderar tre ömsesidigt icke-angränsande hörn har ännu mindre kromatiskt tal, $c(t)=2t$ .

Andra $\chi$ -avgränsade graffamiljer inkluderar:

• De perfekta graferna , med $c(t)=t$
• Graferna för boxicitet två, som är skärningsgraferna för axelparallella rektanglar, med $c(t)\in O(t\log(t))$ ( stor O-notation )
• Graferna för avgränsad klickbredd
• Skärningsgraferna för skalade och översatta kopior av vilken kompakt konvex form som helst i planet
• Polygoncirkelgraferna , med $c(t)=2^{t$ }
• Cirkelgraferna , med $c(t)=7t^{2}$ och (generaliserande cirkeldiagram) "outerstring-graferna", skärningsgrafer för avgränsade kurvor i planet som alla berör den obegränsade ytan av kurvornas arrangemang
• Yttersträngsgrafen är en skärningsgraf av kurvor som ligger i ett gemensamt halvplan och har en ändpunkt på gränsen för det halvplanet
• Skärningsgraferna för kurvor som korsar en fast kurva mellan 1 och $\displaystyle n\in \mathbb {N} }$ { gånger

Men även om skärningsgrafer för konvexa former, cirkelgrafer och yttre stränggrafer alla är specialfall av stränggrafer , är själva stränggraferna inte $\chi$ -avgränsade. De inkluderar som ett specialfall skärningsgraferna för linjesegment , som inte heller är $\chi$ -avgränsade.

Olösta problem

Olöst problem i matematik :

Är alla trädfria grafklasser $\chi$ -begränsade?

(fler olösta problem i matematik)

Enligt Gyárfás–Sumner-förmodan är för varje träd $T$ , de grafer som inte innehåller $T$ som en inducerad subgraf $\chi$ -avgränsade . Detta skulle till exempel inkludera fallet med klofria grafer, eftersom en klo är en speciell sorts träd. Det är dock känt att gissningarna endast gäller vissa speciella träd, inklusive stigar och radie-två-träd.

Ett annat problem med $\chi$$) {\displaystyle c(t) )}$ ställdes av Louis Esperet, som frågade om varje ärftlig klass av grafer som är $\chi$ -limited har en funktion som växer som mest polynom som en funktion av $t$ . Ett starkt motexempel till Esperets gissning tillkännagavs 2022 av Briański, Davies och Walczak, som bevisade att det finns $\chi$ -avgränsade ärftliga klasser vars funktion $c(t)$ kan vara vald godtyckligt så länge den växer snabbare än ett visst kubiskt polynom.

externa länkar

• Chi-gränsad , öppen problemträdgård