The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture

Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang

Research output: Contribution to journalJournal articleResearchpeer-review

132 Downloads (Pure)

Abstract

Let k be an odd natural number ≥5, and let G be a (6k−7)-edge-connected graph of bipartite index at least k−1. Then, for each mapping f:V(G)→N, G has a subgraph H such that each vertex v has H-degree f(v) modulo k. We apply this to prove that, if c:V(G)→Zk is a proper vertex-coloring of a graph G of chromatic number k≥5 or k−1≥6, then each edge of G can be assigned a weight 1 or 2 such that each weighted vertex-degree of G is congruent to c modulo k. Consequently, each nonbipartite (6k−7)-edge-connected graph of chromatic number at most k (where k is any odd natural number ≥3) has an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees (even after reducing these weighted degrees modulo k). We characterize completely the bipartite graph having an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees. In particular, that problem belongs to P while it is NP-complete for nonbipartite graphs. The characterization also implies that every 3-edge-connected bipartite graph with at least 3 vertices has such an edge-labeling, and so does every simple bipartite graph of minimum degree at least 3.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume121
Pages (from-to)308-325
ISSN0095-8956
DOIs
Publication statusPublished - 2016

Keywords

  • Factors modulo k
  • 1-2-3-conjecture

Cite this

@article{bbf7fd4bfd854598b8442a0c1f794b95,
title = "The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture",
abstract = "Let k be an odd natural number ≥5, and let G be a (6k−7)-edge-connected graph of bipartite index at least k−1. Then, for each mapping f:V(G)→N, G has a subgraph H such that each vertex v has H-degree f(v) modulo k. We apply this to prove that, if c:V(G)→Zk is a proper vertex-coloring of a graph G of chromatic number k≥5 or k−1≥6, then each edge of G can be assigned a weight 1 or 2 such that each weighted vertex-degree of G is congruent to c modulo k. Consequently, each nonbipartite (6k−7)-edge-connected graph of chromatic number at most k (where k is any odd natural number ≥3) has an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees (even after reducing these weighted degrees modulo k). We characterize completely the bipartite graph having an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees. In particular, that problem belongs to P while it is NP-complete for nonbipartite graphs. The characterization also implies that every 3-edge-connected bipartite graph with at least 3 vertices has such an edge-labeling, and so does every simple bipartite graph of minimum degree at least 3.",
keywords = "Factors modulo k, 1-2-3-conjecture",
author = "Carsten Thomassen and Yezhou Wu and Cun-Quan Zhang",
year = "2016",
doi = "10.1016/j.jctb.2016.06.010",
language = "English",
volume = "121",
pages = "308--325",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press",

}

The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture. / Thomassen, Carsten; Wu, Yezhou; Zhang, Cun-Quan.

In: Journal of Combinatorial Theory. Series B, Vol. 121, 2016, p. 308-325.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture

AU - Thomassen, Carsten

AU - Wu, Yezhou

AU - Zhang, Cun-Quan

PY - 2016

Y1 - 2016

N2 - Let k be an odd natural number ≥5, and let G be a (6k−7)-edge-connected graph of bipartite index at least k−1. Then, for each mapping f:V(G)→N, G has a subgraph H such that each vertex v has H-degree f(v) modulo k. We apply this to prove that, if c:V(G)→Zk is a proper vertex-coloring of a graph G of chromatic number k≥5 or k−1≥6, then each edge of G can be assigned a weight 1 or 2 such that each weighted vertex-degree of G is congruent to c modulo k. Consequently, each nonbipartite (6k−7)-edge-connected graph of chromatic number at most k (where k is any odd natural number ≥3) has an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees (even after reducing these weighted degrees modulo k). We characterize completely the bipartite graph having an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees. In particular, that problem belongs to P while it is NP-complete for nonbipartite graphs. The characterization also implies that every 3-edge-connected bipartite graph with at least 3 vertices has such an edge-labeling, and so does every simple bipartite graph of minimum degree at least 3.

AB - Let k be an odd natural number ≥5, and let G be a (6k−7)-edge-connected graph of bipartite index at least k−1. Then, for each mapping f:V(G)→N, G has a subgraph H such that each vertex v has H-degree f(v) modulo k. We apply this to prove that, if c:V(G)→Zk is a proper vertex-coloring of a graph G of chromatic number k≥5 or k−1≥6, then each edge of G can be assigned a weight 1 or 2 such that each weighted vertex-degree of G is congruent to c modulo k. Consequently, each nonbipartite (6k−7)-edge-connected graph of chromatic number at most k (where k is any odd natural number ≥3) has an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees (even after reducing these weighted degrees modulo k). We characterize completely the bipartite graph having an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees. In particular, that problem belongs to P while it is NP-complete for nonbipartite graphs. The characterization also implies that every 3-edge-connected bipartite graph with at least 3 vertices has such an edge-labeling, and so does every simple bipartite graph of minimum degree at least 3.

KW - Factors modulo k

KW - 1-2-3-conjecture

U2 - 10.1016/j.jctb.2016.06.010

DO - 10.1016/j.jctb.2016.06.010

M3 - Journal article

VL - 121

SP - 308

EP - 325

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -