Berge–Fulkerson coloring for C(8)‐linked graphs. Issue 1 (8th September 2017)
- Record Type:
- Journal Article
- Title:
- Berge–Fulkerson coloring for C(8)‐linked graphs. Issue 1 (8th September 2017)
- Main Title:
- Berge–Fulkerson coloring for C(8)‐linked graphs
- Authors:
- Hao, Rong‐Xia
Zhang, Cun‐Quan
Zheng, Ting - Abstract:
- Abstract: It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them . Let G be a cubic graph and F = { C 1, …, C r } be a 2‐factor of G such that | C j | is odd if and only if j ≤ 2 k for some integer k . The 2‐factor F is C (8) ‐linked if, for every i ≤ k, there is a circuit D i of length 8 with edge sequence e 1 i … e 8 i where e 1 i, e 5 i ∈ E ( C 2 i − 1 ) and e 3 i, e 7 i ∈ E ( C 2 i ) . And the cubic graph G is C (8) ‐linked if it contains a C (8) ‐linked 2‐factor. It is proved in this article that every C (8) ‐linked cubic graph is Berge–Fulkerson colorable . It is also noticed that many classical families of snarks (including some high oddness snarks) are C (8) ‐linked. Consequently, the Berge–Fulkerson conjecture is verified for these infinite families of snarks.
- Is Part Of:
- Journal of graph theory. Volume 88:Issue 1(2018)
- Journal:
- Journal of graph theory
- Issue:
- Volume 88:Issue 1(2018)
- Issue Display:
- Volume 88, Issue 1 (2018)
- Year:
- 2018
- Volume:
- 88
- Issue:
- 1
- Issue Sort Value:
- 2018-0088-0001-0000
- Page Start:
- 46
- Page End:
- 60
- Publication Date:
- 2017-09-08
- Subjects:
- Berge–Fulkerson conjecture -- Berge–Fulkerson coloring -- oddness -- perfect matching -- snarks -- 4‐flow
Graph theory -- Periodicals
511 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/jgt.22184 ↗
- Languages:
- English
- ISSNs:
- 0364-9024
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 4996.450000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 6175.xml