Linear Bound for Majority Colourings of Digraph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386958" target="_blank" >RIV/00216208:11320/18:10386958 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p29/pdf" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p29/pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Linear Bound for Majority Colourings of Digraph

Popis výsledku v původním jazyce

Given eta in [0,1], a colouring C of V(G) is an eta-majority colouring if at most eta deg^+(v) out-neighbours of v have colour C(v), for any vertex v. We show that every digraph G equipped with an assignment of lists L, each of size at least k, has a 2/k-majority L-colouring. For even k this is best possible, while for odd k the constant 2/k cannot be replaced by any number less than 2/(k+1). This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases k = 3 and k = 4 and claim a weaker result for general k.

Název v anglickém jazyce

Linear Bound for Majority Colourings of Digraph

Popis výsledku anglicky

Given eta in [0,1], a colouring C of V(G) is an eta-majority colouring if at most eta deg^+(v) out-neighbours of v have colour C(v), for any vertex v. We show that every digraph G equipped with an assignment of lists L, each of size at least k, has a 2/k-majority L-colouring. For even k this is best possible, while for odd k the constant 2/k cannot be replaced by any number less than 2/(k+1). This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases k = 3 and k = 4 and claim a weaker result for general k.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA16-19910S" target="_blank" >GA16-19910S: Grafy a zobrazení -- Algebraické vlastnosti grafů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

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

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

25

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

4

Strana od-do

—

Kód UT WoS článku

000442822900003

EID výsledku v databázi Scopus

2-s2.0-85053254029