Mycielskian

Inom det matematiska området för grafteorin är Mycielskian eller Mycielski-grafen för en oriktad graf en större graf som bildas av den genom en konstruktion av Jan Mycielski ( 1955 ) . Konstruktionen bevarar egenskapen att vara triangelfri men ökar det kromatiska talet ; genom att applicera konstruktionen upprepade gånger på en triangelfri startgraf, visade Mycielski att det finns triangelfria grafer med godtyckligt stora kromatiska tal.

Konstruktion

Mycielskisk konstruktion applicerad på en 5- cykelgraf , som producerar Grötzsch-grafen med 11 hörn och 20 kanter, den minsta triangelfria 4-kromatiska grafen ( Chvátal 1974 ).

Låt de n hörnen i den givna grafen G vara v ₁ , v ₂ , . . . , v _n . Mycielski-grafen μ( G ) innehåller själva G som en _subgraf , tillsammans med n +1 ytterligare hörn: en vertex u _i som motsvarar varje vertex vi i G , och en extra vertex w . Varje vertex u _i är förbunden med en kant till w , så att dessa hörn bildar en subgraf i form av en stjärna K _{1, n} . Dessutom, för varje kant v _i v _j av G , inkluderar Mycielski-grafen två kanter, u _i v _j och v _i u _j .

Således, om G har n hörn och m kanter, har μ( G ) 2 n +1 hörn och 3 m + n kanter.

De enda nya trianglarna i μ( G ) är av formen v _i v _j u _k , där v _i v _j v _k är en triangel i G . Således, om G är triangelfri, så är μ( G ).

För att se att konstruktionen ökar det kromatiska talet ${\displaystyle \chi (G)=k} ,$ överväg en korrekt k -färgning av $\mu (G) {-}\{w\}$ ; det vill säga en mappning $c:\{v_{1},\ldots ,v_ {n},u_{1},\ldots ,u_{n}\}\to \{1,2,\ldots ,k\}$ med $c(x) \neq c(y)$ för intilliggande hörn x , y . Om vi hade $c(u_{i})\subset \{1,2,\ldots ,k{-}1\}$ för all i , då skulle vi kunna definiera en riktig ( k −1)-färgning av G med $c'\!(v_{i})=c(u_{i })$ när $c(v_{i})=k$ , och $c'\!(v_{i} )=c(v_{i})$ annars. Men detta är omöjligt för $\chi (G)=k$ , så c måste använda alla k färger för $\{u_{1}, \ldots ,u_{n}\}$ , och eventuell korrekt färgning av den sista vertexen w måste använda en extra färg. Det vill säga $\chi (\mu (G))=k{+}1$ .

Itererade Mycielskians

M ₂ , M ₃ och M ₄ Mycielski grafer

Genom att applicera Mycielskian upprepade gånger, med början med enkantsgrafen, produceras en sekvens av grafer M _i = μ( M _{i −1} ), som ibland kallas Mycielski-graferna. De första graferna i denna sekvens är grafen M ₂ = K ₂ med två hörn förbundna med en kant, cykelgrafen M ₃ = C ₅ , och Grötzsch-grafen M ₄ med 11 hörn och 20 kanter.

är grafen M _i triangelfri , ( i −1)- vertex-ansluten och i - kromatisk . Antalet hörn i M _i för i ≥ 2 är 3 × 2 ^{i −2} − 1 (sekvens A083329 i OEIS ), medan antalet kanter för i = 2, 3, . . . är:

1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (sekvens A122695 i OEIS ).

Egenskaper

Hamiltonsk cykel i M ₄ (Grötzsch-graf)

Om G har kromatiskt tal k , så har μ( G ) kromatiskt tal k + 1 ( Mycielski 1955 ).
Om G är triangelfritt så är μ( G ) det också ( Mycielski 1955 ).
Mer generellt, om G har klicknummer ω( G ), så har μ( G ) klicknummer max(2,ω( G )) ( Mycielski 1955 ).
Om G är en faktorkritisk graf , så är μ( G ) det också ( Došlić 2005) . I synnerhet _är varje graf Mi för i ≥ 2 faktorkritisk.
Om G har en Hamiltonsk cykel , så har μ( G ) det också ( Fisher, McKenna & Boyer 1998) .
Om G har dominansnummer γ( G ), så har μ( G ) dominansnummer γ( G )+1 ( Fisher, McKenna & Boyer 1998 ).

Koner över grafer

En generaliserad mycielskian, bildad som en kon över 5-cykeln, Δ ₃ (C ₅ ) = Δ ₃ (Δ ₂ ( K ₂ )).

En generalisering av mycielskian, kallad en kon över en graf, introducerades av Stiebitz (1985) och studerades vidare av Tardif (2001) och Lin et al. (2006) . I denna konstruktion bildar man en graf Δ _i ( G ) från en given graf G genom att ta tensorprodukten av graferna G × H , där H är en bana av längden i med en självslinga i ena änden, och sedan kollapsa in i en enda supervertex alla hörn som är associerade med toppunkten för H vid den icke-loopände av banan. Mycielskian själv kan bildas på detta sätt som μ( G ) = Δ ₂ ( G ).

Även om konkonstruktionen inte alltid ökar det kromatiska talet, visade Stiebitz (1985) att den gör det när den appliceras iterativt på K ₂ . Det vill säga definiera en sekvens av familjer av grafer, kallade generaliserade Mycielskians, som

₂ ) = { K2 } och ℳ( k +1) = {Δi ₍ G ) | G ∈ ℳ( k ), i ∈

\mathbb {N}

}.

Till exempel är ℳ(3) familjen med udda cykler. Då är varje graf i ℳ( k ) k -kromatisk. Beviset använder metoder för topologisk kombinatorik som utvecklats av László Lovász för att beräkna det kromatiska antalet Kneser-grafer . Den triangelfria egenskapen förstärks sedan enligt följande: om man bara tillämpar konkonstruktionen Δ _i för i ≥ r , så har den resulterande grafen en udda omkrets på minst 2 r + 1, det vill säga den innehåller inga udda cykler med mindre längd än 2 r + 1. Sålunda ger generaliserade mycielsker en enkel konstruktion av grafer med högt kromatiskt tal och hög udda omkrets.

Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Lecture Notes in Mathematics, vol. 406, Springer-Verlag, s. 243–246 .
Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory , 25 (3): 261–266, doi : 10.7151/dmgt.1279 , MR 2232992 .
Fisher, David C.; McKenna, Patricia A.; Boyer, Elizabeth D. (1998), "Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs", Discrete Applied Mathematics , 84 ( 1–3): 93–105, doi : 10.1016/S0166-218X(97) )00126-1 .
Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006), "Several parameters of generalized Mycielskians", Discrete Applied Mathematics , 154 (8): 1173–1182, doi : 10.1016/j.dam.2005.11.001 .
Mycielski, Jan (1955), "Sur le coloriage des graphes" (PDF) , Colloq. Matematik. , 3 (2): 161–162, doi : 10.4064/cm-3-2-161-162 .
Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen , Habiliteringsuppsats, Technische Universität Ilmenau . Som citeras av Tardif (2001) .
Tardif, C. (2001), "Fractional chromatic numbers of cones over graphs", Journal of Graph Theory , 38 (2): 87–94, doi : 10.1002/jgt.1025 .

externa länkar

Weisstein, Eric W. "Mycielski Graph" . MathWorld .