RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Zametki, 2002, Volume 72, Issue 1, Pages 35–37 (Mi mz401)  

This article is cited in 1 scientific paper (total in 1 paper)

Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces

O. V. Borodina, A. V. Kostochkaa, A. Raspaudb, E. Sopenab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Université Bordeaux 1

Abstract: A coloring of the vertices of a graph is called acyclic if the ends of each edge are colored in distinct colors, and there are no two-colored cycles. Suppose each face of rank $k$, $k\ge 4$, in a map on a surface $S^N$ is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on $N$ and $k$. In the present paper we prove a sharper estimate $55(-Nk)^{4/7}$ for the number of colors provided that $k\ge 1$ and $-N\ge 5^7k^{4/3}$.

DOI: https://doi.org/10.4213/mzm401

Full text: PDF file (163 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 2002, 72:1, 31–42

Bibliographic databases:

UDC: 519.174
Received: 29.08.2001

Citation: O. V. Borodin, A. V. Kostochka, A. Raspaud, E. Sopena, “Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces”, Mat. Zametki, 72:1 (2002), 35–37; Math. Notes, 72:1 (2002), 31–42

Citation in format AMSBIB
\Bibitem{BorKosRas02}
\by O.~V.~Borodin, A.~V.~Kostochka, A.~Raspaud, E.~Sopena
\paper Estimating the Minimal Number of Colors in Acyclic -Strong Colorings of Maps on Surfaces
\jour Mat. Zametki
\yr 2002
\vol 72
\issue 1
\pages 35--37
\mathnet{http://mi.mathnet.ru/mz401}
\crossref{https://doi.org/10.4213/mzm401}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1942579}
\zmath{https://zbmath.org/?q=an:1021.05036}
\transl
\jour Math. Notes
\yr 2002
\vol 72
\issue 1
\pages 31--42
\crossref{https://doi.org/10.1023/A:1019808819476}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000178299100003}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0141848613}


Linking options:
  • http://mi.mathnet.ru/eng/mz401
  • https://doi.org/10.4213/mzm401
  • http://mi.mathnet.ru/eng/mz/v72/i1/p35

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Radoicic R. Toth G., “The Discharging Method in Combinatorial Geometry and the Pach-Sharir Conjecture”, Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, 453, ed. Goodman J. Pach J. Pollack R., Amer Mathematical Soc, 2008, 319–342  crossref  mathscinet  zmath  isi
  • Математические заметки Mathematical Notes
    Number of views:
    This page:237
    Full text:86
    References:40
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020