Dinitz-probléma

A matematika, azon belül a kombinatorika és gráfelmélet területén a Dinitz-probléma (Dinitz-sejtés, Galvin-tétel) táblázatok részletes latin négyzetté kiterjesztéséről szóló állítás, amit 1979-ben Jeff Dinitz állított fel,^[1] majd 1994-ben Fred Galvin igazolt.^[2]^[3]

A Dinitz-probléma szerint ha adott egy n × n-es négyzetes táblázat, m különböző szimbólum, ahol m ≥ n, a táblázat minden cellájába az m szimbólumból kiválasztott n elemű halmaz kerül, lehetséges úgy megválasztani a cellákba kerülő szimbólumokat (úgy címkézni velük a cellákat), hogy egyetlen sorban vagy oszlopban se ismétlődjenek a címkék.

Megfogalmazható gráfelméleti eredményként is, eszerint a $K_{n,n}$ teljes páros gráf lista-élkromatikus száma éppen $n$ . Tehát ha a teljes páros gráf minden éléhez egy-egy $n$ színből álló halmazt rendelünk, lehetséges minden egyes élhez a hozzárendelt színek közül egy-egyet úgy kiválasztani, hogy az azonos csúcsból kiinduló élek közül ne legyen azonos színű.

Galvin általánosabb állítást bizonyít, miszerint bármely páros multigráf lista-élkromatikus száma megegyezik az élkromatikus számával. Egy általánosabb lista-élszínezési sejtés szerint ugyanez nem csak a páros gráfokra, hanem tetszőleges hurokmentes multigráfra igaz. Egy még általánosabb sejtés szerint pedig a karommentes gráfok listakromatikus száma minden esetben megegyezik a kromatikus számukkal.^[4] A Galvin-tétel kapcsolódik továbbá Rota bázisokkal kapcsolatos sejtéséhez.^[5]

Fordítás

Ez a szócikk részben vagy egészben a Dinitz conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Erdős, P.; A. L. Rubin, H. Taylor (1979). „Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata” (PDF). Choosability in graphs (Congressus Numerantium) 26: 125–157. [2016. március 9-i dátummal az eredetiből archiválva]. Hozzáférés: 2018. március 17.
↑ F. Galvin (1995). „The list chromatic index of a bipartite multigraph” (PDF). Journal of Combinatorial Theory 63 (1), 153–158. o. DOI:10.1006/jctb.1995.1011. ^{[halott link]}
↑ Zeilberger, D. (1996). „The method of undetermined generalization and specialization illustrated with Fred Galvin's amazing proof of the Dinitz conjecture”. American Mathematical Monthly 103 (3), 233–239. o. DOI:10.2307/2975373.
↑ Gravier, Sylvain, Frédéric Maffray (2004). „On the choice number of claw-free perfect graphs”. Discrete Mathematics 276 (1-3), 211–218. o. DOI:10.1016/S0012-365X(03)00292-9. MR 2046636.
↑ Chow, T. Y. (1995). „On the Dinitz conjecture and related conjectures” (PDF). Discrete Mathematics 145 (1–3), 73–82. o. DOI:10.1016/0012-365X(94)00055-N.

További információk

Weisstein, Eric W.: Dinitz Problem (angol nyelven). Wolfram MathWorld

[Erdős-1] Erdős, P.; A. L. Rubin, H. Taylor (1979). „Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata” (PDF). Choosability in graphs (Congressus Numerantium) 26: 125–157. [2016. március 9-i dátummal az eredetiből archiválva]. Hozzáférés: 2018. március 17.

[Galvin-2] F. Galvin (1995). „The list chromatic index of a bipartite multigraph” (PDF). Journal of Combinatorial Theory 63 (1), 153–158. o. DOI:10.1006/jctb.1995.1011. ^{[halott link]}

[Zeilberger-3] Zeilberger, D. (1996). „The method of undetermined generalization and specialization illustrated with Fred Galvin's amazing proof of the Dinitz conjecture”. American Mathematical Monthly 103 (3), 233–239. o. DOI:10.2307/2975373.

[Gravier-4] Gravier, Sylvain, Frédéric Maffray (2004). „On the choice number of claw-free perfect graphs”. Discrete Mathematics 276 (1-3), 211–218. o. DOI:10.1016/S0012-365X(03)00292-9. MR 2046636.

[Chow-5] Chow, T. Y. (1995). „On the Dinitz conjecture and related conjectures” (PDF). Discrete Mathematics 145 (1–3), 73–82. o. DOI:10.1016/0012-365X(94)00055-N.

[1]

[2]

[3]

[4]

[5]