RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2019 Volume 488, Pages 31–48 (Mi znsl6911)

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



© Steklov Math. Inst. of RAS, 2024