2016/02/09 by Robert Lukoťka, Lukoťka, Robert, Ján Mazák +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Surface Chemistry and Catalysis
paper · pdf · doi:10.48550/arxiv.1602.02949
openalex publication_date 2016/02/09 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We introduce weak oddness \ω textrm w, a new measure of\nuncolourability of cubic graphs, defined as the least number of odd components\nin an even factor. For every bridgeless cubic graph G,\n\ρ(G)\≤\ω textrm w(G)\≤\ω(G), where \ρ(G) denotes the\nresistance of G and \ω(G) denotes the oddness of G, so this new\nmeasure is an approximation of both oddness and resistance. We demonstrate that\nthere are graphs G satisfying \ρ(G) < \ω textrm w(G) < \ω(G),\nand that the difference between any two of those three measures can be\narbitrarily large. The construction implies that if we replace a vertex of a\ncubic graph with a triangle, then its oddness can decrease by an arbitrarily\nlarge amount.\n