Geodesic
On proper edge $3$-colorings of a cubic graph
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 31-48
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{ZNSL_2019_488_a1,
     author = {D. V. Karpov},
     title = {On proper edge $3$-colorings of a cubic graph},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {31--48},
     year = {2019},
     volume = {488},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a1/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - On proper edge $3$-colorings of a cubic graph
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 31
EP  - 48
VL  - 488
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a1/
LA  - ru
ID  - ZNSL_2019_488_a1
ER  - 
%0 Journal Article
%A D. V. Karpov
%T On proper edge $3$-colorings of a cubic graph
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 31-48
%V 488
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a1/
%G ru
%F ZNSL_2019_488_a1
D. V. Karpov. On proper edge $3$-colorings of a cubic graph. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 31-48. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a1/

[1] Yu. V. Matiyasevich, “Odin kriterii raskrashivaemosti vershin, formuliruemyi v terminakh orientatsii reber”, Diskretnyi analiz, 1974, no. 26, 65–71 | Zbl

[2] N. Alon, “Combinatorial Nullstelensats”, Combinatorics, Probability and Computing, 8 (1999), 7–29 | DOI | MR | Zbl

[3] G. Chartrand, A. Kaugars, D. R. Lick, “Critically $n$-connected graphs”, Proc. Amer. Math. Soc., 32:1 (1972), 63–68 | MR

[4] D. V. Karpov, A. V. Pastor, “O strukture $k$-svyaznogo grafa”, Zap. nauchn. semin. POMI, 266, 2000, 76–106

[5] W. T. Tutte, Connectivity in graphs, Univ. Toronto Press, Toronto, 1966 | MR | Zbl

[6] F. Kharari, Teoriya grafov, “Mir”, M., 1973; F. Harary, Graph theory, 1969