About: Let [Formula: see text] be the class of d-degenerate graphs and let L be a list assignment for a graph G. A colouring of G such that every vertex receives a colour from its list and the subgraph induced by vertices coloured with one color is a d-degenerate graph is called the [Formula: see text]-colouring of G. For a k-uniform list assignment L and [Formula: see text], a graph G is equitably [Formula: see text]-colorable if there is an [Formula: see text]-colouring of G such that the size of any colour class does not exceed [Formula: see text]. An equitable [Formula: see text]-colouring is a generalization of an equitable list coloring, introduced by Kostochka et al., and an equitable list arboricity presented by Zhang. Such a model can be useful in the network decomposition where some structural properties on subnets are imposed. In this paper we give a polynomial-time algorithm that for a given (k, d)-partition of G with a t-uniform list assignment L and [Formula: see text], returns its equitable [Formula: see text]-colouring. In addition, we show that 3-dimensional grids are equitably [Formula: see text]-colorable for any t-uniform list assignment L where [Formula: see text].   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • Let [Formula: see text] be the class of d-degenerate graphs and let L be a list assignment for a graph G. A colouring of G such that every vertex receives a colour from its list and the subgraph induced by vertices coloured with one color is a d-degenerate graph is called the [Formula: see text]-colouring of G. For a k-uniform list assignment L and [Formula: see text], a graph G is equitably [Formula: see text]-colorable if there is an [Formula: see text]-colouring of G such that the size of any colour class does not exceed [Formula: see text]. An equitable [Formula: see text]-colouring is a generalization of an equitable list coloring, introduced by Kostochka et al., and an equitable list arboricity presented by Zhang. Such a model can be useful in the network decomposition where some structural properties on subnets are imposed. In this paper we give a polynomial-time algorithm that for a given (k, d)-partition of G with a t-uniform list assignment L and [Formula: see text], returns its equitable [Formula: see text]-colouring. In addition, we show that 3-dimensional grids are equitably [Formula: see text]-colorable for any t-uniform list assignment L where [Formula: see text].
Subject
  • Graph theory
  • Internet architecture
  • Mathematical concepts
  • Graph invariants
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software