{
  "id": "2002.05288",
  "version": "v1",
  "published": "2020-02-13T00:06:43.000Z",
  "updated": "2020-02-13T00:06:43.000Z",
  "title": "Graphs with multi-$4$-cycles and the Barnette's conjecture",
  "authors": [
    "Jan Florek"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let ${\\cal H}$ denote the family of all graphs with multi-$4$-cycles and suppose that $G \\in {\\cal H}$. Then, $G$ is a bipartite graph with a vertex bipartition $\\{V_{\\alpha}, V_{\\beta}\\}$. We prove that for every vertex $v \\in V_{\\beta}$ and for every $2$-colouring $V_{\\alpha} \\rightarrow \\{1, 2\\}$ there exists a $2$-colouring $V_{\\beta} \\rightarrow \\{1, 2\\}$ such that every cycle in $G$ is not monochromatic and $b(v) = 1$ ($b(v) = 2$). Let now $G$ be a simple even plane triangulation with a vertex $3$-partition $\\{V_{1}, V_{2}, V_{3}\\}$. Denote by $B_{i}$, $i = 1, 2, 3$, the set of all vertices in $V_i$ of degree at least $6$ in $G$. Suppose that $G[B_{1}\\cup B_{3}]$ ($G[B_{2}\\cup B_{3}]$) is a subgraph of $G$ induced by the set $B_{1}\\cup B_{3}$ ($B_{2}\\cup B_{3}$, respectively). Let $G^{*}$ be the dual graph of $G$ with the following $3$-face-colouring: a face $f$ of $G^{*}$ is coloured with $i$ if and only if the vertex $v = f^{*} \\in V_{i}$. We prove that if $H = G[B_{1}\\cup B_{3}] \\cup G[B_{2}\\cup B_{3}] \\in {\\cal H}$, then, for any edge chosen on a face coloured $3$ and of size at least $6$ in $G^{*}$, there exists a Hamilton cycle of $G^{*}$ which avoids this edge. Moreover, if every component of $H$ is $2$-connected, then there exists a Hamilton cycle of $G^{*}$ such that for every face coloured $3$ it avoids every second edge of this face or it avoids at most two edges of this face.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-13T00:06:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C45",
      "05C75"
    ],
    "keywords": [
      "barnettes conjecture",
      "hamilton cycle",
      "second edge",
      "bipartite graph",
      "edge chosen"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}