Nowhere-zero $3$-flow of graphs with small independence number Article Swipe

PDF

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1707.06745

Tutte's $3$-flow conjecture states that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we characterize all graphs with independence number at most $4$ that admit a nowhere-zero $3$-flow. The characterization of $3$-flow verifies Tutte's $3$-flow conjecture for graphs with independence number at most $4$ and with order at least $21$. In addition, we prove that every odd-$5$-edge-connected graph with independence number at most $3$ admits a nowhere-zero $3$-flow. To obtain these results, we introduce a new reduction method to handle odd wheels.

Related Topics

Concepts

Independence number Mathematics Combinatorics Conjecture Flow (mathematics) Discrete mathematics Independence (probability theory) Graph Zero (linguistics) Geometry Statistics Philosophy Linguistics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1707.06745
PDF: https://arxiv.org/pdf/1707.06745
OA Status: green
Cited By: 1
References: 5
Related Works: 10
OpenAlex ID: https://openalex.org/W2737661774

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2737661774

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.1707.06745

Digital Object Identifier
Title: Nowhere-zero $3$-flow of graphs with small independence number

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2017

Year of publication
Publication date: 2017-07-21

Full publication date if available
Authors: Jiaao Li, Rong Luo, Yi Wang

List of authors in order
Landing page: https://arxiv.org/abs/1707.06745

Publisher landing page
PDF URL: https://arxiv.org/pdf/1707.06745

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/1707.06745

Direct OA link when available
Concepts: Independence number, Mathematics, Combinatorics, Conjecture, Flow (mathematics), Discrete mathematics, Independence (probability theory), Graph, Zero (linguistics), Geometry, Statistics, Philosophy, Linguistics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2020: 1

Per-year citation counts (last 5 years)
References (count): 5

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2737661774
doi	https://doi.org/10.48550/arxiv.1707.06745
ids.doi	https://doi.org/10.48550/arxiv.1707.06745
ids.mag	2737661774
ids.openalex	https://openalex.org/W2737661774
fwci
type	preprint
title	Nowhere-zero $3$-flow of graphs with small independence number
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T11476
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9994999766349792
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2608
topics[1].subfield.display_name	Geometry and Topology
topics[1].display_name	Graph theory and applications
topics[2].id	https://openalex.org/T11329
topics[2].field.id	https://openalex.org/fields/26
topics[2].field.display_name	Mathematics
topics[2].score	0.9991999864578247
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2607
topics[2].subfield.display_name	Discrete Mathematics and Combinatorics
topics[2].display_name	Limits and Structures in Graph Theory
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2984853995
concepts[0].level	3
concepts[0].score	0.7749074101448059
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1060343
concepts[0].display_name	Independence number
concepts[1].id	https://openalex.org/C33923547
concepts[1].level	0
concepts[1].score	0.7050442695617676
concepts[1].wikidata	https://www.wikidata.org/wiki/Q395
concepts[1].display_name	Mathematics
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.6764261722564697
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C2780990831
concepts[3].level	2
concepts[3].score	0.5425221920013428
concepts[3].wikidata	https://www.wikidata.org/wiki/Q319141
concepts[3].display_name	Conjecture
concepts[4].id	https://openalex.org/C38349280
concepts[4].level	2
concepts[4].score	0.5300486087799072
concepts[4].wikidata	https://www.wikidata.org/wiki/Q1434290
concepts[4].display_name	Flow (mathematics)
concepts[5].id	https://openalex.org/C118615104
concepts[5].level	1
concepts[5].score	0.5227920413017273
concepts[5].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[5].display_name	Discrete mathematics
concepts[6].id	https://openalex.org/C35651441
concepts[6].level	2
concepts[6].score	0.5041176080703735
concepts[6].wikidata	https://www.wikidata.org/wiki/Q625303
concepts[6].display_name	Independence (probability theory)
concepts[7].id	https://openalex.org/C132525143
concepts[7].level	2
concepts[7].score	0.47928351163864136
concepts[7].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[7].display_name	Graph
concepts[8].id	https://openalex.org/C2780813799
concepts[8].level	2
concepts[8].score	0.46513479948043823
concepts[8].wikidata	https://www.wikidata.org/wiki/Q3274237
concepts[8].display_name	Zero (linguistics)
concepts[9].id	https://openalex.org/C2524010
concepts[9].level	1
concepts[9].score	0.11326655745506287
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[9].display_name	Geometry
concepts[10].id	https://openalex.org/C105795698
concepts[10].level	1
concepts[10].score	0.06868022680282593
concepts[10].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[10].display_name	Statistics
concepts[11].id	https://openalex.org/C138885662
concepts[11].level	0
concepts[11].score	0.06367376446723938
concepts[11].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[11].display_name	Philosophy
concepts[12].id	https://openalex.org/C41895202
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q8162
concepts[12].display_name	Linguistics
keywords[0].id	https://openalex.org/keywords/independence-number
keywords[0].score	0.7749074101448059
keywords[0].display_name	Independence number
keywords[1].id	https://openalex.org/keywords/mathematics
keywords[1].score	0.7050442695617676
keywords[1].display_name	Mathematics
keywords[2].id	https://openalex.org/keywords/combinatorics
keywords[2].score	0.6764261722564697
keywords[2].display_name	Combinatorics
keywords[3].id	https://openalex.org/keywords/conjecture
keywords[3].score	0.5425221920013428
keywords[3].display_name	Conjecture
keywords[4].id	https://openalex.org/keywords/flow
keywords[4].score	0.5300486087799072
keywords[4].display_name	Flow (mathematics)
keywords[5].id	https://openalex.org/keywords/discrete-mathematics
keywords[5].score	0.5227920413017273
keywords[5].display_name	Discrete mathematics
keywords[6].id	https://openalex.org/keywords/independence
keywords[6].score	0.5041176080703735
keywords[6].display_name	Independence (probability theory)
keywords[7].id	https://openalex.org/keywords/graph
keywords[7].score	0.47928351163864136
keywords[7].display_name	Graph
keywords[8].id	https://openalex.org/keywords/zero
keywords[8].score	0.46513479948043823
keywords[8].display_name	Zero (linguistics)
keywords[9].id	https://openalex.org/keywords/geometry
keywords[9].score	0.11326655745506287
keywords[9].display_name	Geometry
keywords[10].id	https://openalex.org/keywords/statistics
keywords[10].score	0.06868022680282593
keywords[10].display_name	Statistics
keywords[11].id	https://openalex.org/keywords/philosophy
keywords[11].score	0.06367376446723938
keywords[11].display_name	Philosophy
language	en
locations[0].id	pmh:oai:arXiv.org:1707.06745
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/1707.06745
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/1707.06745
locations[1].id	doi:10.48550/arxiv.1707.06745
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.1707.06745
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5072223743
authorships[0].author.orcid	https://orcid.org/0000-0002-4771-2094
authorships[0].author.display_name	Jiaao Li
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I12097938
authorships[0].affiliations[0].raw_affiliation_string	Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States#TAB#
authorships[0].institutions[0].id	https://openalex.org/I12097938
authorships[0].institutions[0].ror	https://ror.org/011vxgd24
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I12097938
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	West Virginia University
authorships[0].author_position	first
authorships[0].raw_author_name	Jiaao Li
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States#TAB#
authorships[1].author.id	https://openalex.org/A5066405314
authorships[1].author.orcid	https://orcid.org/0000-0002-5237-1001
authorships[1].author.display_name	Rong Luo
authorships[1].countries	CN, US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I12097938
authorships[1].affiliations[0].raw_affiliation_string	Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States
authorships[1].affiliations[1].institution_ids	https://openalex.org/I118574674
authorships[1].affiliations[1].raw_affiliation_string	School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, China
authorships[1].institutions[0].id	https://openalex.org/I118574674
authorships[1].institutions[0].ror	https://ror.org/051hvcm98
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I118574674
authorships[1].institutions[0].country_code	CN
authorships[1].institutions[0].display_name	Jiangsu Normal University
authorships[1].institutions[1].id	https://openalex.org/I12097938
authorships[1].institutions[1].ror	https://ror.org/011vxgd24
authorships[1].institutions[1].type	education
authorships[1].institutions[1].lineage	https://openalex.org/I12097938
authorships[1].institutions[1].country_code	US
authorships[1].institutions[1].display_name	West Virginia University
authorships[1].author_position	middle
authorships[1].raw_author_name	Rong Luo
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States, School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, Jiangsu, 221116, China
authorships[2].author.id	https://openalex.org/A5101469989
authorships[2].author.orcid	https://orcid.org/0000-0002-8569-0703
authorships[2].author.display_name	Yi Wang
authorships[2].countries	CN
authorships[2].affiliations[0].institution_ids	https://openalex.org/I143868143
authorships[2].affiliations[0].raw_affiliation_string	School of Mathematical Sciences, Anhui University, Hefei, Anhui 230601, China
authorships[2].institutions[0].id	https://openalex.org/I143868143
authorships[2].institutions[0].ror	https://ror.org/05th6yx34
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I143868143
authorships[2].institutions[0].country_code	CN
authorships[2].institutions[0].display_name	Anhui University
authorships[2].author_position	last
authorships[2].raw_author_name	Yi Wang
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	School of Mathematical Sciences, Anhui University, Hefei, Anhui 230601, China
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/1707.06745
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Nowhere-zero $3$-flow of graphs with small independence number
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2767039348, https://openalex.org/W3125750421, https://openalex.org/W4300899577, https://openalex.org/W3194471551, https://openalex.org/W4375956809, https://openalex.org/W1581373162, https://openalex.org/W2784911598, https://openalex.org/W2950390960, https://openalex.org/W2114143805, https://openalex.org/W4303105543
cited_by_count	1
counts_by_year[0].year	2020
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1707.06745
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/1707.06745
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/1707.06745
primary_location.id	pmh:oai:arXiv.org:1707.06745
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/1707.06745
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/1707.06745
publication_date	2017-07-21
publication_year	2017
referenced_works	https://openalex.org/W1484040084, https://openalex.org/W2011470163, https://openalex.org/W2039100101, https://openalex.org/W2023859733, https://openalex.org/W2098621549
referenced_works_count	5
abstract_inverted_index.a	9, 27, 67, 76
abstract_inverted_index.In	12, 52
abstract_inverted_index.To	70
abstract_inverted_index.at	22, 43, 49, 63
abstract_inverted_index.of	32
abstract_inverted_index.to	80
abstract_inverted_index.we	15, 54, 74
abstract_inverted_index.$3$	65
abstract_inverted_index.$4$	24, 45
abstract_inverted_index.The	30
abstract_inverted_index.all	17
abstract_inverted_index.and	46
abstract_inverted_index.for	38
abstract_inverted_index.new	77
abstract_inverted_index.odd	82
abstract_inverted_index.most	23, 44, 64
abstract_inverted_index.that	4, 25, 56
abstract_inverted_index.this	13
abstract_inverted_index.with	19, 40, 47, 60
abstract_inverted_index.$21$.	51
abstract_inverted_index.admit	26
abstract_inverted_index.every	5, 57
abstract_inverted_index.graph	7, 59
abstract_inverted_index.least	50
abstract_inverted_index.order	48
abstract_inverted_index.prove	55
abstract_inverted_index.these	72
abstract_inverted_index.admits	8, 66
abstract_inverted_index.graphs	18, 39
abstract_inverted_index.handle	81
abstract_inverted_index.method	79
abstract_inverted_index.number	21, 42, 62
abstract_inverted_index.obtain	71
abstract_inverted_index.paper,	14
abstract_inverted_index.states	3
abstract_inverted_index.Tutte's	0, 35
abstract_inverted_index.wheels.	83
abstract_inverted_index.$3$-flow	1, 33, 36
abstract_inverted_index.results,	73
abstract_inverted_index.verifies	34
abstract_inverted_index.$3$-flow.	11, 29, 69
abstract_inverted_index.addition,	53
abstract_inverted_index.introduce	75
abstract_inverted_index.reduction	78
abstract_inverted_index.conjecture	2, 37
abstract_inverted_index.characterize	16
abstract_inverted_index.independence	20, 41, 61
abstract_inverted_index.nowhere-zero	10, 28, 68
abstract_inverted_index.characterization	31
abstract_inverted_index.$4$-edge-connected	6
abstract_inverted_index.odd-$5$-edge-connected	58
cited_by_percentile_year
countries_distinct_count	2
institutions_distinct_count	3
citation_normalized_percentile