Choosability of Graphs with Infinite Sets of Forbidden Differences

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004685" target="_blank" >RIV/00216208:11320/07:00004685 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Choosability of Graphs with Infinite Sets of Forbidden Differences

Original language description

The notion of list-T-coloring is a common generalization of T-coloring and list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c such that the color c(v) of each vertex v is contained in its list L(v) and |c(u)-c(v)| notin T for any two adjacent vertices u and v. The T-choice number of a graph G is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors. We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T-choice number of K_2 isfinite. For the case when the T-choice number of K_2 is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and the other being polynomial in the T-choice n

Czech name

Vybíravost grafů s nekonečnými množinami zakázaných rozdílů

Czech description

Koncept T-vybíravosti je společným zobecněním T-barevnosti a vybíravosti. Pro množinu T nezáporných celých čísel, graf G a a přiřazení seznamů čísel jednotlivým vrcholům L řekneme, že graf G je T-obarvitelný z přiřazení seznamů L pokud existuje obarveníc vrcholů grafu G takové, že pro každý vrchol v je c(v) prvkem L(v) a pro každou hranu uv platí |c(u)-c(v)| notin T. T-vybíravost grafu G je nejmenší číslo k takové, že G je T-obarvitelný pro libovolné přiřazení seznamů L, které každému vrcholu přiřazuje množinu o alespoň k prvcích. V článku se zaměřujeme na T-vybíravost grafů pro T nekonečnou. Ukážeme, že pro libovolnou pevnou množinu celých čísel T platí, že T-vybíravost je konečná pro všechny grafy právě tehdy když je konečná pro K_2. Pro případ, kdy je T-vybíravost K_2 konečná, ukážeme dva horní odhady pro T-vybíravost libovolného grafu G - jeden polynomiální v maximálním stupni grafu G, druhý polynomiální v T-vybíravosti grafu K_2.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Volume of the periodical

307

Issue of the periodical within the volume

23

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

8

Pages from-to

3040-3047

UT code for WoS article

—

EID of the result in the Scopus database

—