This article is cited in
1 paper
On proper edge $3$-colorings of a cubic graph
D. V. Karpovab a Saint Petersburg State University
b St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
Abstract:
We study
defining edge sets of a cubic graph (i.e. edge sets which
$3$-coloring uniquely determines a proper edge
$3$-coloring of this cubic graph). We prove that a cubic graph with
$3n$ edges has a defining set of
$n$ edges. For a
$3$-connected plane cubic graph with
$3n$ edges, each face of which has at most
$d$ vertices, it is proved that there exists a defining set of at most
$n - {n-2d+3\over 3d-8}$ edges. In both cases, we describe an algorithm constructing the desired defining set.
For a connected cubic graph
$G$ with
$3n$ edges, we construct a series of polynomials over
$\mathbb{F}_3$ in
$n+1$ variables such that each of them does not vanish identically if and only if there exists a proper edge
$3$-coloring of
$G$. In the end of this paper, it is proved that a cubic multigraph
$G$ on
$2n$ vertices has at most
$3\cdot 2^n$ proper edge
$3$-colorings. This bound is tight. In the case where
$G$ has at most one pair of multiple edges, it is proved that
$G$ has at most
$9\cdot 2^{n-2}$ proper edge
$3$-colorings.
Key words and phrases:
cubic graph, $3$-edge coloring.
UDC:
519.174.7
Received: 26.11.2019