Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Flow-critical Graphs
Author: da Silva C.N.
Lucchesi C.L.
Abstract: In this paper we introduce the concept of k-flow-critical graphs. These are graphs that do not admit a k-flow but such that any smaller graph obtained from it by contraction of edges or of pairs of vertices is k-flowable. Any minimal counter-example for Tutte's 3-Flow and 5-Flow Conjectures must be 3-flow-critical and 5-flow-critical, respectively. Thus, any progress towards establishing good characterizations of k-flow-critical graphs can represent progress in the study of these conjectures. We present some interesting properties satisfied by k-flow-critical graphs discovered recently. © 2008 Elsevier B.V. All rights reserved.
Rights: fechado
Identifier DOI: 10.1016/j.endm.2008.01.029
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-39349089794.pdf168.19 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.