Generalized arboricity of graphs with large girth

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

Abstract

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
Tomasz Bartnicki,,
-
, Bartłomiej Bosek
Bartłomiej Bosek,,
-
, Sebastian Czerwiński
Sebastian Czerwiński,,
-
, Michał Farnik
Michał Farnik,,
-
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Zofia Miechowicz
Zofia Miechowicz,,
-
Journal seriesDiscrete Mathematics, ISSN 0012-365X, (A 25 pkt)
Issue year2019
Vol342
No5
Pages1343-1350
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
DOIDOI:10.1016/j.disc.2019.01.018
URL https://www.sciencedirect.com/science/article/pii/S0012365X19300299
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 05-06-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.005; WoS Impact Factor: 2017 = 0.738 (2) - 2017=0.796 (5)
Citation count*
Cite
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.
Back