Počet záznamov: 1
Decompositions and reductions of snarks
Názov Decompositions and reductions of snarks Aut.údaje R. Nedela, M. Skoviera Autor Nedela Roman 1960- (50%) UMBFP12 - Inštitút matematiky a informatiky
Spoluautori Škoviera Martin (50%)
Zdroj.dok. Journal of graph theory. Vol. 22, no. 3 (1996), pp. 253-279. - Hoboken : John Wiley & Sons, 1996 Kľúč.slová matematika - mathematics grafy - charts - graphs Jazyk dok. angličtina Krajina Slovenská republika Systematika 51 Anotácia According to M. Gardner [''Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem,'' Scientific American, vol. 234 (1976), pp. 126-130], a snark is a nontrivial cubic graph whose edges cannot be properly colored by three colors. The problem of what ''nontrivial'' means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k-edge-cut producing components G(1) and G(2), then either one of G(1) and G(2) is not 3-edge-colorable, or by adding a ''small'' number of vertices to either component one can obtain snarks <(G)over tilde (1)> and <(G)over tilde (2)> whose order does not exceed that of G. The two situations lead to a definition of a L-reduction and k-decomposition of G. Snarks that for m < k do not admit m-reductions, m-decompositions, or both are k-irreducible, k-indecomposable, and k-simple, rAccording to M. Gardner [''Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem,'' Scientific American, vol. 234 (1976), pp. 126-130], a snark is a nontrivial cubic graph whose edges cannot be properly colored by three colors. The problem of what ''nontrivial'' means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k-edge-cut producing components G(1) and G(2), then either one of G(1) and G(2) is not 3-edge-colorable, or by adding a ''small'' number of vertices to either component one can obtain snarks <(G)over tilde (1)> and <(G)over tilde (2)> whose order does not exceed that of G. The two situations lead to a definition of a L-reduction and k-decomposition of G. [...] Kategória publikačnej činnosti ADE Číslo archívnej kópie 28530 Kategória ohlasu BRINKMANN, Gunnar - GOEDGEBEUR, Jan - HAGGLUND, Jonas - MARKSTROM, Klas. Generation and properties of snarks. In Journal of combinatorial theory series B. ISSN 0095-8956, 2013, vol. 103, no. 4, pp. 468-488.
MACAJ, Martin - MAZAK, Jan. Asymptotic lower bounds on circular chromatic index of snarks. In Electronic journal of combinatorics [online]. 2013, vol. 20, no. 2, [cit. 2014-02-28]. ISSN 1077-8926. Dostupné na: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p2
KUTNAR, Klavdija - MARUSIC, Dragan - NAIMZADA, A. K. et al. Some Topics in Graph Theory. In Networks, topology and dynamics : theory and applications to economics and social systems. Berlin : Springer Verlag, 2009. ISBN 978-3-540-68407-7, pp. 3-22.
BROERSMA, Hajo - FIJAVZ, Gasper - KAISER, Tomas et al. Contractible subgraphs, Thomassen´s conjecture and the dominating cycle conjecture for snarks. In Discrete mathematics. ISSN 0012-365X, 2008, vol. 308, no. 24, pp. 6064-6077.
PATAKFALVI, Zsolt. Line-graphs of cubic graphs are normal. In Discrete mathematics. ISSN 0012-365X, 2008, vol. 308, no. 12, pp. 2351-2365.
MADARAS, Tomas - SOTAK, Roman. More maps of p-gons with a ring of q-gons. In Ars combinatoria. ISSN 0381-7032, 2007, vol. 85, pp. 395-403.
BRADLEY, R.C. On the number of colorings of a snark minus an edge. In Journal of graph theory. ISSN 0364-9024, 2006, vol. 51, no. 3, pp. 251-259.
MYNHARDT, C.M. - BURGER, A.P. - CLARK, T.C. et al. Altitude of regular graphs with girth at least five. In Discrete mathematics. ISSN 0012-365X, 2005, vol. 294, no. 3, pp. 241-257.
POTOCNIK, P. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. In Journal of combinatorial theory series B. ISSN 0095-8956, 2004, vol. 91, no. 2, pp. 289-300.
DVORAK, Z. - KARA, J. - KRAL, D. et al. An algorithm for cyclic edge connectivity of cubic graphs. In Algorithm theory - SWAT 2004. Berlin : Springer Verlag, 2004. ISBN 3-540-22339-8, pp. 236-247.
CAVICCHIOLI, A. - MURGOLO, T.E. - RUINI, B. - SPAGGIARI, F. Special classes of snarks. In Acta applicandae mathematicae. ISSN 0167-8019, 2003, vol. 76, no. 1, pp. 57-88.
STEFFEN, E. Non-bicritical critical snarks. In Graphs and combinatorics. ISSN 0911-0119, 1999, vol. 15, no. 4, pp. 473-480.
BRINKMANN, G. - STEFFEN, E. Snarks and reducibility. In Ars combinatoria. ISSN 0381-7032, 1998, vol. 50, pp. 292-296.
STEFFEN, E. Classifications and characterizations of snarks. In Discrete mathematics. ISSN 0012-365X, 1998, vol. 188, no. 1-3, pp. 183-203.
CAVICCHIOLI, A. - MESCHIARI, M. - RUINI, B. - SPAGGIARI, F. A survey on snarks and new results : products, reducibility and a computer search. In Journal of graph theory. ISSN 0364-9024, 1998, vol. 28, no. 2, pp. 57-86.
BROERSMA, H. - FIJAVŽ, G. - KAISER, T. et al. Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks. In Electronic Notes in Discrete Mathematics [online]. 2007, vol. 28, pp. 55-59 [cit. 2014-02-28]. ISSN 1571-0653. Dostupné na: http://www.sciencedirect.com/science/article/pii/S0012365X07009387.
FIOL, M.A. - VILALTELLA, J. Some results on the structure of multipoles in the study of snarks. In Electronic journal of combinatorics [online]. 2015, vol. 22, no. 1, article no. P1.45 [cit. 2015-04-27]. ISSN 1077-8926. Dostupné na: http://arxiv.org/pdf/1308.0480v1.pdf
STEFFEN, Eckhard. On bicritical snarks. In Mathematica slovaca. ISSN 0139-9918, 2001, vol. 51, no. 2, pp. 141-150.
GRÜNEWALD, Stefan - STEFFEN, Eckhard. Cyclically 5-edge connected non-bicritical critical snarks. In Discussiones mathematicae graph theory. ISSN 1234-3099, 1999, vol. 19, no. 1, pp. 5-11.
HRNČIAR, Pavel. On color-closed multipoles. In Acta Universitatis Matthiae Belii : series mathematics, vol. 7. Banská Bystrica : Univerzita Mateja Bela, 1999. ISBN 80-8055-347-5, pp. 31-34.
Katal.org. BB301 - Univerzitná knižnica Univerzity Mateja Bela v Banskej Bystrici Báza dát xpca - PUBLIKAČNÁ ČINNOSŤ Odkazy PERIODIKÁ-Súborný záznam periodika 
článok
Počet záznamov: 1