Zapiski Nauchnykh Seminarov POMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (240 kB) Citations (1)
References:
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
Document Type: Article
UDC: 519.174.7
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Kar19}
\by D.~V.~Karpov
\paper On proper edge $3$-colorings of a cubic graph
\inbook Combinatorics and graph theory. Part~XI
\serial Zap. Nauchn. Sem. POMI
\yr 2019
\vol 488
\pages 31--48
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl6911}
Linking options:
  • https://www.mathnet.ru/eng/znsl6911
  • https://www.mathnet.ru/eng/znsl/v488/p31
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:91
    Full-text PDF :32
    References:26
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024