Mycielskian - Mycielskian

V matematický oblast teorie grafů, Mycielskian nebo Mycielskiho graf z neorientovaný graf je větší graf z něj vytvořený konstrukcí Jan Mycielski  (1955 ). Stavba zachovává majetek bytí bez trojúhelníků ale zvyšuje chromatické číslo; opakovaným použitím konstrukce na počáteční trojúhelníkový graf, Mycielski ukázal, že existují grafy bez trojúhelníků s libovolně velkým chromatickým číslem.

Konstrukce

Mycielskian konstrukce aplikována na 5-graf cyklu, vyrábějící Grötzschův graf s 11 vrcholy a 20 hranami, nejmenší 4-chromatický graf bez trojúhelníků (Chvátal 1974 ).

Nech n vrcholy daného grafu G být proti₁, proti₂, . . . , proti_n. Mycielskiho graf μ (G) obsahuje G sám sebe jako podgraf spolu s n+1 další vrcholy: vrchol u_i odpovídající každému vrcholu proti_i z Ga další vrchol w. Každý vrchol u_i je spojen hranou s w, takže tyto vrcholy tvoří podgraf ve formě hvězdy K._1,n. Navíc pro každou hranu proti_iproti_j z G, graf Mycielski obsahuje dvě hrany, u_iproti_j a proti_iu_j.

Pokud tedy G má n vrcholy a m hrany, μ (G) má 2n+1 vrcholy a 3m+n hrany.

Jediné nové trojúhelníky v μ (G) jsou ve formě proti_iproti_ju_k, kde proti_iproti_jproti_k je trojúhelník v G. Pokud tedy G je bez trojúhelníků, takže je μ (G).

Chcete-li vidět, že konstrukce zvyšuje chromatické číslo ${displaystyle chi (G) = k}$, považujte za správné k-barvení ${displaystyle mu (G) {-} {w}}$; tj. mapování ${displaystyle c: {v_ {1}, ldots, v_ {n}, u_ {1}, ldots, u_ {n}} o {1,2, ldots, k}}$ s ${displaystyle c (x) eq c (y)}$ pro sousední vrcholy X,y. Kdybychom měli ${displaystyle c (u_ {i}) podmnožina {1,2, ldots, k {-} 1}}$ pro všechny i, pak bychom mohli definovat vlastní (k-1) - zbarvení G podle ${displaystyle c '! (v_ {i}) = c (u_ {i})}$ když ${displaystyle c (v_ {i}) = k}$, a ${displaystyle c '! (v_ {i}) = c (v_ {i})}$ v opačném případě. Ale to je nemožné ${displaystyle chi (G) = k}$, tak C musí použít vše k barvy pro ${displaystyle {u_ {1}, ldots, u_ {n}}}$a jakékoli správné zbarvení posledního vrcholu w musí použít zvláštní barvu. To znamená, ${displaystyle chi (mu (G)) = k {+} 1}$.

Iterovali jsme Mycielskianů

M₂, M₃ a M₄ Mycielski grafy

Opakované použití Mycielskian, počínaje grafem s jednou hranou, vytváří sled grafů M_i = μ (M_i−1), někdy nazývané Mycielski grafy. Prvních několik grafů v tomto pořadí je graf M₂ = K.₂ se dvěma vrcholy spojenými hranou, graf cyklu M₃ = C₅a Grötzschův graf M₄ s 11 vrcholy a 20 hranami.

Obecně platí, že graf M_i je bez trojúhelníků, (i−1)-připojen k vrcholu, a i-chromatický. Počet vrcholů v M_i pro i ≥ 2 je 3 × 2ⁱ⁻² - 1 (sekvence A083329 v OEIS ), zatímco počet hran pro i = 2, 3,. . . je:

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

Vlastnosti

Hamiltonovský cyklus v M₄ (Grötzschův graf)

• Li G má chromatické číslo k, pak μ (G) má chromatické číslo k + 1 (Mycielski 1955 ).
• Li G je bez trojúhelníků, pak je také μ (G) (Mycielski 1955 ).
• Obecněji, pokud G má číslo kliky ω (G), pak μ (G) má číslo kliky max (2, ω (G)).(Mycielski 1955 ).
• Li G je faktorově kritický graf, pak je také μ (G) (Došlić 2005 ). Zejména každý graf M_i pro i ≥ 2 je faktorově kritický.
• Li G má Hamiltonovský cyklus, pak také μ (G) (Fisher, McKenna & Boyer 1998 ).
• Li G má dominantní číslo γ (G), pak μ (G) má dominantní číslo γ (G)+1. (Fisher, McKenna & Boyer 1998 ).

Kužele nad grafy

Zobecněný Mycielskian, vytvořený jako kužel během 5-cyklu, Δ₃(C₅) = Δ₃(Δ₂(K.₂)).

Zobecnění Mycielskian, nazvaný kužel přes graf, byl představen Stiebitz (1985) a dále studoval Tardif (2001) a Lin a kol. (2006). V této konstrukci jeden vytvoří graf Δ_i(G) z daného grafu G tím, že tenzorový součin grafů G × H, kde H je cesta délky i se samostatnou smyčkou na jednom konci a poté se zhroutí do jednoho supervertexu všechny vrcholy spojené s vrcholem H na konci cesty bez smyčky. Samotný Mycielskian může být vytvořen tímto způsobem jako μ (G) = Δ₂(G).

I když konstrukce kužele ne vždy zvyšuje chromatické číslo, Stiebitz (1985) prokázal, že tak činí při iterativní aplikaci na K.₂. To znamená, definujte posloupnost rodin grafů, nazývaných zobecněné Mycielskians, as

ℳ (2) = {K.₂} a ℳ (k+1) = {Δ_i(G) | G ∈ ℳ (k), i ∈ ℕ}.

Například ℳ (3) je rodina lichých cyklů. Pak každý graf v ℳ (k) je k-chromatický. Důkaz používá metody topologická kombinatorika vyvinutý uživatelem László Lovász vypočítat chromatický počet Kneserovy grafy Vlastnost bez trojúhelníků je poté posílena následovně: pokud se použije pouze konstrukce kužele Δ_i pro i ≥ r, pak výsledný graf má zvláštní obvod alespoň 2r + 1, to znamená, že neobsahuje žádné liché cykly o délce menší než 2r + 1. Takto zobecnění Mycielskians poskytují jednoduchou konstrukci grafů s vysokým chromatickým číslem a vysokým lichým obvodem.

Reference

• Chvátal, Vašek (1974), „Minimalita Mycielského grafu“, Grafy a kombinatorika (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973)Přednášky z matematiky, 406, Springer-Verlag, str. 243–246.
• Došlić, Tomislav (2005), „Mycielskians and matchings“, Diskuse Mathematicae Graph Theory, 25 (3): 261–266, doi:10,7151 / dmgt.1279, PAN  2232992.
• Fisher, David C .; McKenna, Patricia A .; Boyer, Elizabeth D. (1998), „Hamiltonicita, průměr, dominance, balení a biclique rozdělení Mycielskiho grafů“, Diskrétní aplikovaná matematika, 84 (1–3): 93–105, doi:10.1016 / S0166-218X (97) 00126-1.
• Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006), „Několik parametrů zobecněných Mycielskianů“, Diskrétní aplikovaná matematika, 154 (8): 1173–1182, doi:10.1016 / j.dam.2005.11.001.
• Mycielski, Jan (1955), „Sur le coloriage des graphes“ (PDF), Colloq. Matematika., 3: 161–162.
• Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Habilitační práce, Technische Universität Ilmenau. Jak uvádí Tardif (2001).
• Tardif, C. (2001), "Frakční chromatické počty kuželů nad grafy", Journal of Graph Theory, 38 (2): 87–94, doi:10,1002 / jgt.1025.

externí odkazy

• Weisstein, Eric W. „Mycielski Graph“. MathWorld.