Generalized arboricity of graphs with large girth
Tomasz Bartnicki , Bartłomiej Bosek , Sebastian Czerwiński , Michał Farnik , Jarosław Grytczuk , Zofia Miechowicz
AbstractThe 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.
|Journal series||Discrete Mathematics, ISSN 0012-365X, (N/A 100 pkt)|
|Publication size in sheets||0.5|
|Keywords in English||Arboricity; Acyclic chromatic index; Bounded expansion; Entropy compression|
|Score||= 100.0, 09-01-2020, ArticleFromJournal|
|Publication indicators||= 0; = 0; : 2018 = 1.042; : 2018 = 0.728 (2) - 2018=0.756 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.