304 KB18 KB200820252016Chen, FuyuanNing, Boštevilka:1letnik:10str. 91-98COBISSID:17734233ISSN:1855-3966URN:URN:NBN:SI:doc-VTEH5KLNenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaceloštevilski toknikjer-ničeln 3-tokorientacija po modulu 3povezavni reziA note on nowhere-zero 3-flows and Zsub3-connectivity|There are many major open problems in integer flow theory, such as Tutte's 3-flow conjecture that every 4-edge-connected graph admits a nowhere-zero 3-flow, Jaeger et al.'s J. Comb. Theory, Ser. B 56, No. 2, 165--182 (1992) conjecture that every 5-edge-connected graph is ?$Z_3$?-connected and Kochol's J. Comb. Theory, Ser. B 83, No. 2, 258--261 (2001) conjecture that every bridgeless graph with at most three 3-edge-cuts admits a nowhere-zero 3-flow (an equivalent version of 3-flow conjecture). C. Thomassen J. Comb. Theory, Ser. B 102, No. 2, 521--529 (2012) proved that every 8-edge-connected graph is ?$Z_3$?-connected and therefore admits a nowhere-zero 3-flow. Furthermore, Lovász et al. J. Comb. Theory, Ser. B 103, No. 5, 587--598 (2013) improved Thomassen's result to 6-edge-connected graphs. In this paper, we prove that: (1) Every 4-edge-connected graph with at most seven 5-edge-cuts admits a nowhere-zero 3-flow. (2) Every bridgeless graph containing no 5-edge-cuts but at most three 3-edge-cuts admits a nowhere-zero 3-flow. (3) Every 5-edge-connected graph with at most five 5-edge-cuts is ?$Z_3$?-connected. Our main theorems are partial results to Tutte's 3-flow conjecture, Kochol's conjecture and Jaeger et al.'s conjecture, respectivelyV teoriji celoštevilskih tokov je veliko odprtih problemov, kot so Tuttejeva domneva o 3-toku, po kateri vsak 4-povezavno-povezan graph dopušča nikjer-ničeln 3-tok, domneva Jaegerja in soavtorjev, da je vsak 5-povezavnopovezan graf ?$Z_3$?-povezan, in Kocholova domneva, da vsak brezmostni graf z največ tremi 3-povezavnimi-rezi dopušča nikjer-ničelni 3-tok (ekvivalentna različica domneve o 3-toku). Thomassen je dokazal, da je vsak 8-povezavno-povezan graf ?$Z_3$?-povezan in da zato dopušča nikjer-ničeln 3-tok. Nadalje so Lovasz, Thomassen, Wu in Zhang izboljšali Thomassenov rezultat na 6-povezavno-povezane grafe. V članku dokažemo, da: (1) Vsak 4-povezavno-povezan graf z največ sedmimi 5-povezavnimi-rezi dopušča nikjer-ničelni 3-tok. (2) Vsak brezmostni graf, ki ne vsebuje nobenih 5-povezavnihrezov, vsebuje pa največ tri 3-povezavne-reze dopušča nikjerničelni 3-tok. (3) Vsak 5-povezavno-povezani graf z največ petimi 5-povezavnimi-rezi je ?$Z_3$?-povezan. Naši glavni izreki predstavljajo delne rezultate za Tuttejevo domnevo o 3-toku, za Kocholovo domnevo ter za domnevo Jaegerja in soavtorjevTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije