390 KB57 KB200820252020Bonvicini, SimonaVietri, Andrealetnik:19številka:2str. 209-229ISSN:1855-3974COBISSID_HOST:44008963URN:URN:NBN:SI:doc-D1FRV4TYenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneabarvanje povezavcritical graphedge-colouringkritični grafMöbius stripMöbiusov trakA Möbius-type gluing technique for obtaining edge-critical graphs|Using a technique which is inspired by topology, we construct original examples of 3- and 4-edge critical graphs. The 3-critical graphs cover all even orders starting from 26; the 4-critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3-critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg's infinite family of 3-critical graphs, Chetwynd's 4-critical graph of order 16 and Fiol's 4-critical graph of order 18S pomočjo tehnike, za katero smo dobili idejo v topologiji, konstruiramo izvirne primere 3- in 4-povezavno kritičnih grafov. 3-kritične grafe dobimo za vse sode rede začenši s 26; 4-kritične grafe dobimo za vse sode rede od 20 dalje ter za vse lihe rede. Posebej, naši 3-kritični grafi niso izomorfni tistim, s katerimi je Goldberg ovrgel t.i. domnevo o kritičnem grafu. Z uporabo istega pristopa pregledamo tudi konstrukcijo nekaterih osnovnih kritičnih grafov, kot so Goldbergova neskončna družina 3-kritičnih grafov, Chetwyndov 4-kritični graf reda 16 in Fiolov 4-kritični graf reda 18TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije