Flow-critical snarks

• Grant number: 13/06137-8
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2013
• End date: May 31, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Candida Nunes da Silva
• Grantee: Breno Lima de Freitas
• Host Institution: Centro de Ciências e Tecnologias para a Sustentabilidade (CCTS). Universidade Federal de São Carlos (UFSCAR). Sorocaba , SP, Brazil

Abstract

This is a project on k-(edge)-flow-critical graphs, which are graphs that do not admit a k-flow but the graph obtained after contracting any of its edges do admit a k-flow. We will focus on the study of snarks, that are cubic graphs that do not admit a 3-edge-colouring -- neither a 4-flow -- as Tutte has shown that a cubic graph admits a 3-edge-colouring if and only if it admits a 4-flow. Several celebrated conjectures can be reduced to snarks, thus motivating a lot of study on the structure of such graphs. Tutte's 5-Flow Conjecture, which asserts that every 2-edge-connected graph has a 5-flow, is one of such conjectures. A recent paper due to Silva, Pesci and Lucchesi observes that every 4-flow-critical snark does admit a 5-flow and that the non 4-flow-critical ones must have a 4-flow-critical snark as a minor. Such facts suggest a new research approach towards the resolution of Tutte's 5-Flow Conjecture. The aim of this project is to start research following this new approach by investigating for the class of snarks whether there is any relation between (I) being 4-flow-critical and being hipohamiltonian, i. e., not being hamiltonian but becaming hamiltonian after the deletion of any of its vertices; or (II) being 4-flow-critical and being bicritical, i. e., a graph that does not have a 3-edge-colouring but the graph obtained after the deletion of any pair of its vertices has one. (AU)