Equitable list vertex colourability and arboricity of grids

Ewa Drgas-Burchardt , Janusz Dybizbański , Hanna Furmańczyk , Elżbieta Sidorowicz

Abstract

A graph G is equitably k-list arborable if for any k-uniform list assignment L, there is an equitable L-colouring of G whose each colour class induces an acyclic graph. The smallest number k admitting such a coloring is named equitable list vertex arboricity and is denoted by ρ=l(G). Zhang in 2016 posed the conjecture that if k≥ d(∆(G)+1)/2e then G is equitably k-list arborable. We give some new tools that arehelpful in determining values of k for which a general graph is equitably k-list arborable. We use them to prove the Zhang’s conjecture for d-dimensional grids where d∈{2,3,4} and give new bounds onρ=l(G) for general graphs and for d-dimensional grids with d≥5.
Author Ewa Drgas-Burchardt
Ewa Drgas-Burchardt,,
-
, Janusz Dybizbański (FMPI / II)
Janusz Dybizbański,,
- Institute of Informatics
, Hanna Furmańczyk (FMPI / II)
Hanna Furmańczyk,,
- Institute of Informatics
, Elżbieta Sidorowicz
Elżbieta Sidorowicz,,
-
Journal seriesFilomat, ISSN 0354-5180, (A 25 pkt)
Issue year2018
Vol32
No18
Pages6353-6374
Publication size in sheets1.05
ASJC Classification2600 General Mathematics
DOIDOI:10.2298/FIL1818353D
URL http://www.pmf.ni.ac.rs/filomat-content/2018/32-18/32-18-18-8510.pdf
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 07-04-2019, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 07-04-2019, ArticleFromJournal
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2017 = 0.813; WoS Impact Factor: 2017 = 0.635 (2) - 2017=0.857 (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