|
Zapiski Nauchnykh Seminarov POMI, 2019, Volume 488, Pages 31–48
(Mi znsl6911)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Received: 26.11.2019
Citation:
D. V. Karpov, “On proper edge $3$-colorings of a cubic graph”, Combinatorics and graph theory. Part XI, Zap. Nauchn. Sem. POMI, 488, POMI, St. Petersburg, 2019, 31–48
Linking options:
https://www.mathnet.ru/eng/znsl6911 https://www.mathnet.ru/eng/znsl/v488/p31
|
Statistics & downloads: |
Abstract page: | 91 | Full-text PDF : | 32 | References: | 26 |
|