An edge set of a cubic graph is said to be defining if a 3-coloring of it uniquely determines a proper edge 3-coloring of the graph. It is proved that a cubic graph with 3n edges has a defining set of n edges. It is also proved that for a 3-connected plane cubic graph with 3n edges, each face of which has at most d vertices, there exists a defining set of at most n−n−2d+33d−8documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ n-rac{n-2d+3}{3d-8} $$end{document} edges. In both cases, an algorithm finding the desired defining set is constructed.For a connected cubic graph G with 3n edges, a series of polynomials over the field ğ”½3 in n+1 variables is defined so that each of them does not vanish identically if and only if there exists a proper edge 3-coloring of G.Finally, it is proved that a cubic multigraph G on 2n vertices has at most 3 · 2n 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 · 2n−2 proper edge 3-colorings.
展开▼
