About: Equitable d-degenerate Choosability of Graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Equitable d-degenerate Choosability of Graphs Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Equitable d-degenerate Choosability of Graphs
Creator	Drgas-Burchardt, Ewa Furmańczyk, Hanna Sidorowicz, Elżbieta
Source	PMC
abstract	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].
has issue date	2020-04-30(xsd:dateTime)
bibo:doi	10.1007/978-3-030-48966-3_19
has license	no-cc
sha1sum (hex)	dddccf91be0bed6a4aa950d2cb6484cd8c2d30e0
schema:url	https://doi.org/10.1007/978-3-030-48966-3_19
resource representing a document's title	Equitable d-degenerate Choosability of Graphs
has PubMed Central identifier	PMC7254909
schema:publication	Combinatorial Algorithms
resource representing a document's body	covid:dddccf91be0bed6a4aa950d2cb6484cd8c2d30e0#body_text
is schema:about of	named entity 'colorable' named entity 'graph' named entity 'generalization' named entity 'Such' named entity 'algorithm' named entity 'induced' named entity 'WHERE' named entity 'GRAPHS' named entity 'D D' named entity 'GRAPH' named entity 'partition' named entity 'equitable' named entity 'list' named entity 'coloured' named entity 'paper' named entity 'graph' named entity 'partition' named entity 'dimensional' named entity 'minimum degree' named entity 'graph' named entity 'lopp' named entity 'algorithm' named entity 'graph theory' named entity 'Cartesian product' named entity 'graph' named entity '3-dimensional' named entity 'vertices' named entity 'graph' named entity 'graph' named entity 'vertices' named entity 'vertices' named entity 'integer' named entity 'vertex set' named entity 'vertices' named entity 'graph' named entity 'subgraph' named entity '3-dimensional' named entity 'polynomial-time algorithm' named entity 'algorithm' named entity 'non-empty' named entity 'vertices' named entity 'graph' named entity 'vertices' named entity 'graph' named entity 'vertices' named entity 'algorithm' named entity 'vertices' named entity 'minimum degree' named entity 'vertices' named entity 'edge set' named entity 'polynomial-time algorithm' named entity 'Proposition 1' named entity 'choosability' named entity 'algorithm' named entity 'polynomial-time algorithm' named entity 'vertices' named entity 'subgraph' named entity 'vertices' named entity 'vertices' named entity 'vertex' named entity '3-dimensional' named entity 'choosability' named entity 'open question' named entity 'cardinality' named entity 'vertices' named entity 'vertices' named entity 'choosability' named entity 'algorithm' named entity 'vertex' named entity 'vertices' named entity 'graph' named entity 'vertices' named entity 'vertices' named entity 'polynomial-time algorithm' named entity 'vertices' named entity 'graph' named entity 'G 2' named entity 'social network' named entity 'acyclic' named entity 'list colouring' named entity 'arboricity'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

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