{
  "id": "2003.13139",
  "version": "v1",
  "published": "2020-03-29T21:04:59.000Z",
  "updated": "2020-03-29T21:04:59.000Z",
  "title": "The 1-2-3 Conjecture holds for graphs with large enough minimum degree",
  "authors": [
    "Jakub Przybyło"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A simple graph more often than not contains adjacent vertices with equal degrees. This in particular holds for all pairs of neighbours in regular graphs, while a lot such pairs can be expected e.g. in many random models. Is there a universal constant $K$, say $K=3$, such that one may always dispose of such pairs from any given connected graph with at least three vertices by blowing its selected edges into at most $K$ parallel edges? This question was first posed in 2004 by Karo\\'nski, {\\L}uczak and Thomason, who equivalently asked if one may assign weights $1,2,3$ to the edges of every such graph so that adjacent vertices receive distinct weighted degrees - the sums of their incident weights. This basic problem is commonly referred to as the 1-2-3 Conjecture nowadays, and has been addressed in multiple papers. Thus far it is known that weights $1,2,3,4,5$ are sufficient [J. Combin. Theory Ser. B 100 (2010) 347-349]. We show that this conjecture holds if only the minimum degree $\\delta$ of a graph is large enough, i.e. when $\\delta = \\Omega(\\log\\Delta)$, where $\\Delta$ denotes the maximum degree of the graph. The principle idea behind our probabilistic proof relies on associating random variables with a special and carefully designed distribution to most of the vertices of a given graph, and then choosing weights for major part of the edges depending on the values of these variables in a deterministic or random manner.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-29T21:04:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C78"
    ],
    "keywords": [
      "conjecture holds",
      "minimum degree",
      "contains adjacent vertices",
      "vertices receive distinct weighted degrees",
      "adjacent vertices receive distinct"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}