Nowhere-zero 4-flow in almost Petersen-minor free graphs

Xiaofeng Wang; Cun Quan Zhang; Taoye Zhang

doi:10.1016/j.disc.2007.11.055

Nowhere-zero 4-flow in almost Petersen-minor free graphs

Xiaofeng Wang
, Cun Quan Zhang
, Taoye Zhang

Penn State Scranton

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let (P₁₀)_{over(μ, ̄)} be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless (P₁₀)_{over(3, ̄)}-minor free graph admits a nowhere-zero 4-flow.

Original language	English (US)
Pages (from-to)	1025-1032
Number of pages	8
Journal	Discrete Mathematics
Volume	309
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2007.11.055
State	Published - Mar 28 2009

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.11.055

Cite this

@article{f52c6a7702a84e389163d8a56ddf539c,

title = "Nowhere-zero 4-flow in almost Petersen-minor free graphs",

abstract = "Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let (P10)over(μ,{\= }) be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless (P10)over(3,{\= })-minor free graph admits a nowhere-zero 4-flow.",

author = "Xiaofeng Wang and Zhang, \{Cun Quan\} and Taoye Zhang",

note = "Funding Information: The second author was partially supported by the National Security Agency under Grant MSPR-03G-023 and a WV-RCG grant. ",

year = "2009",

month = mar,

day = "28",

doi = "10.1016/j.disc.2007.11.055",

language = "English (US)",

volume = "309",

pages = "1025--1032",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Nowhere-zero 4-flow in almost Petersen-minor free graphs

AU - Wang, Xiaofeng

AU - Zhang, Cun Quan

AU - Zhang, Taoye

N1 - Funding Information: The second author was partially supported by the National Security Agency under Grant MSPR-03G-023 and a WV-RCG grant.

PY - 2009/3/28

Y1 - 2009/3/28

N2 - Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let (P10)over(μ, ̄) be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless (P10)over(3, ̄)-minor free graph admits a nowhere-zero 4-flow.

AB - Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let (P10)over(μ, ̄) be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless (P10)over(3, ̄)-minor free graph admits a nowhere-zero 4-flow.

UR - https://www.scopus.com/pages/publications/60549098664

UR - https://www.scopus.com/pages/publications/60549098664#tab=citedBy

U2 - 10.1016/j.disc.2007.11.055

DO - 10.1016/j.disc.2007.11.055

M3 - Article

AN - SCOPUS:60549098664

SN - 0012-365X

VL - 309

SP - 1025

EP - 1032

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -

Nowhere-zero 4-flow in almost Petersen-minor free graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this