Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 5, Pages 26–33 (Mi da584)  

This article is cited in 15 scientific papers (total in 15 papers)

Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12

O. V. Borodin

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
References:
Abstract: Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al., 2002). This conjecture, if proved, would imply both Borodin's acyclic 5-color theorem (1979) and Thomassen's 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-choosable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (Borodin, Kostochka, and Woodall, 1999) and acyclically 3-choosable (Borodin et al., 2009).
A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le S$. Here, we prove that every planar graph with no cycles with length from 4 to 12 is acyclically 3-choosable. Bibl. 18.
Keywords: planar graph, acyclic coloring, acyclic choosability.
Received: 13.05.2009
Revised: 17.06.2009
English version:
Journal of Applied and Industrial Mathematics, 2010, Volume 4, Issue 2, Pages 158–162
DOI: https://doi.org/10.1134/S1990478910020031
Bibliographic databases:
UDC: 519.172.2
Language: Russian
Citation: O. V. Borodin, “Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 26–33; J. Appl. Industr. Math., 4:2 (2010), 158–162
Citation in format AMSBIB
\Bibitem{Bor09}
\by O.~V.~Borodin
\paper Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12
\jour Diskretn. Anal. Issled. Oper.
\yr 2009
\vol 16
\issue 5
\pages 26--33
\mathnet{http://mi.mathnet.ru/da584}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2590752}
\zmath{https://zbmath.org/?q=an:1249.05107}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 2
\pages 158--162
\crossref{https://doi.org/10.1134/S1990478910020031}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77953484802}
Linking options:
  • https://www.mathnet.ru/eng/da584
  • https://www.mathnet.ru/eng/da/v16/i5/p26
  • This publication is cited in the following 15 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024