Critical and flow-critical snarks coincide

DOI10.7151/DMGT.2204zbMATH Open1458.05096arXiv1709.08111OpenAlexW2962868279MaRDI QIDQ2227110FDOQ2227110

Authors: E. Máčajová, Martin Škoviera 

Publication date: 10 February 2021

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: Over the past twenty years, critical and bicritical snarks have been appearing in the literature in various forms and in different contexts. Two main variants of criticality of snarks have been studied: criticality with respect to the non-existence of a $3$-edge-colouring and criticality with respect to the non-existence of a nowhere-zero $4$-flow. In this paper we show that these two kinds of criticality coincide, thereby completing previous partial results of de Freitas et al. [Electron. Notes Discrete Math. 50 (2015), 199--204] and Fiol et al. [ arXiv:1702.07156v1 (2017)].

Full work available at URL: https://arxiv.org/abs/1709.08111

Recommendations

• Non-bicritical critical snarks
• 3-critical subgraphs of snarks
• Cyclically 5-edge connected non-bicritical critical snarks
• Snarks and flow-snarks constructed from coloring-snarks.
• scientific article; zbMATH DE number 1737273

zbMATH Keywords

cubic graphnowhere-zero flowsnarkedge-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21)

Cites Work

• House of Graphs: a database of interesting graphs
• Graph theory
• Decompositions and reductions of snarks
• Classification and characterizations of snarks
• Generation and properties of snarks
• Non-bicritical critical snarks
• A faster test for 4-flow-criticality in snarks
• Hypohamiltonian snarks have a 5-flow
• Flow-Critical Graphs
• On edge-maps whose inverse preserves flows or tensions
• Snarks and reducibility
• Measures of edge-uncolorability of cubic graphs
• Title not available (Why is that?)
• Factorisation of snarks
• Decomposition of snarks
• Cyclically 5-edge connected non-bicritical critical snarks

Cited In (6)

• Flow resistance to resistance ratios in cubic graphs
• Morphology of small snarks
• A faster test for 4-flow-criticality in snarks
• Hypohamiltonian snarks have a 5-flow
• Title not available (Why is that?)
• Non-bicritical critical snarks

Uses Software

• House of Graphs

This page was built for publication: Critical and flow-critical snarks coincide

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227110)