Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports]
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



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






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


Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2020, Volume 17, Pages 513–520
DOI: https://doi.org/10.33048/semi.2020.17.032
(Mi semr1227)
 

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

Discrete mathematics and mathematical cybernetics

Colouring planar graphs with bounded monochromatic components

A. N. Glebov

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Full-text PDF (141 kB) Citations (1)
References:
Abstract: Borodin and Ivanova proved that every planar graph of girth at least 7 is 2-choosable with the property that each monochromatic component is a path with at most 3 vertices. Axenovich et al. proved that every planar graph of girth 6 is 2-choosable so that each monochromatic component is a path with at most 15 vertices. We improve both these results by showing that planar graphs of girth at least 6 are 2-choosable so that each monochromatic component is a path with at most 3 vertices. Our second result states that every planar graph of girth 5 is 2-choosable so that each monochromatic component is a tree with at most 515 vertices. Finally, we prove that every graph with fractional arboricity at most $\frac{2d+2}{d+2}$ is 2-choosabale with the property that each monochromatic component is a tree with maximum degree at most $d$. This implies that planar graphs of girth 5, 6, and 8 are 2-choosable so that each monochromatic component is a tree with maximum degree at most 4, 2, and 1, respectively. All our results are obtained by applying the Nine Dragon Tree Theorem, which was recently proved by Jiang and Yang, and the Strong Nine Dragon Tree Conjecture partially confirmed by Kim et al. and Moore.
Keywords: planar graph, defective colouring, clustered colouring, list colouring, girth, maximum average degree, forest decomposition, fractional arboricity, Nine Dragon Tree Theorem.
Funding agency Grant number
Russian Science Foundation 16-11-10054
The work is supported by the Russian Science Foundation (project 16-11-10054).
Received December 12, 2019, published April 8, 2020
Bibliographic databases:
Document Type: Article
UDC: 519.172.2, 519.174
MSC: 05C10, 05C15, 05C70
Language: English
Citation: A. N. Glebov, “Colouring planar graphs with bounded monochromatic components”, Sib. Èlektron. Mat. Izv., 17 (2020), 513–520
Citation in format AMSBIB
\Bibitem{Gle20}
\by A.~N.~Glebov
\paper Colouring planar graphs with bounded monochromatic components
\jour Sib. \`Elektron. Mat. Izv.
\yr 2020
\vol 17
\pages 513--520
\mathnet{http://mi.mathnet.ru/semr1227}
\crossref{https://doi.org/10.33048/semi.2020.17.032}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000525534700001}
Linking options:
  • https://www.mathnet.ru/eng/semr1227
  • https://www.mathnet.ru/eng/semr/v17/p513
  • 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
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024