Generalized arboricity of graphs with large girth

Tomasz Bartnicki , Bartłomiej Bosek , Sebastian Czerwiński , Michał Farnik , Jarosław Grytczuk , Zofia Miechowicz


The arboricity of a graph is the least number of colors needed to color the edges of so that no cycle is monochromatic. We consider a higher order analog of this parameter, denoted by , introduced recently by Nešetřil et al. (2014). It is defined as the least number of colors needed to color the edges of a graph so that each cycle gets at least colors. So, is the usual arboricity of , while can be seen as a relaxed version of the acyclic chromatic index of . By the results of Nešetřil et al. (2014) it follows that is bounded for classes of graphs with bounded expansion, provided that the girth of graphs is sufficiently large (depending on ). Using more direct approach we obtain explicit upper bounds on for some classes of graphs. In particular, we prove that for every planar graph of girth at least . A similar result holds for graphs with arbitrary fixed genus. We also demonstrate that for outerplanar graphs, which is best possible. By using entropy compression argument we prove that for graphs of maximum degree and sufficiently large girth.
Author Tomasz Bartnicki - [Uniwersytet Zielonogórski]
Tomasz Bartnicki,,
, Bartłomiej Bosek - [Uniwersytet Jagielloński w Krakowie (UJ)]
Bartłomiej Bosek,,
- Uniwersytet Jagielloński w Krakowie
, Sebastian Czerwiński - [Uniwersytet Zielonogórski (UZ)]
Sebastian Czerwiński,,
- Uniwersytet Zielonogórski
, Michał Farnik - [Uniwersytet Jagiellonski w Krakowie]
Michał Farnik,,
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Zofia Miechowicz - [Uniwersytet Zielonogórski]
Zofia Miechowicz,,
Journal seriesDiscrete Mathematics, ISSN 0012-365X, (N/A 100 pkt)
Issue year2019
Publication size in sheets0.5
Keywords in EnglishArboricity; Acyclic chromatic index; Bounded expansion; Entropy compression
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 09-01-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.042; WoS Impact Factor: 2018 = 0.728 (2) - 2018=0.756 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?