Graphs of low average degree without independent transversals

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F23%3A43966771" target="_blank" >RIV/49777513:23520/23:43966771 - isvavai.cz</a>

Výsledek na webu

<a href="https://onlinelibrary.wiley.com/doi/epdf/10.1002/jgt.22876" target="_blank" >https://onlinelibrary.wiley.com/doi/epdf/10.1002/jgt.22876</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/jgt.22876" target="_blank" >10.1002/jgt.22876</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Graphs of low average degree without independent transversals

Popis výsledku v původním jazyce

An independent transversal of a graph G with a vertex partition P is an independent set of G intersecting each block of P in a single vertex. Wanless and Wood proved that if each block of P has size at least t and the average degree of vertices in each block is at most t/4, then an independent transversal of P exists. We present a construction showing that this result is optimal: for any ε&gt;0 and sufficiently large t, there is a family of forests with vertex partitions whose block size is at least t, average degree of vertices in each block is at most (1/4+ε)t, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.

Název v anglickém jazyce

Graphs of low average degree without independent transversals

Popis výsledku anglicky

An independent transversal of a graph G with a vertex partition P is an independent set of G intersecting each block of P in a single vertex. Wanless and Wood proved that if each block of P has size at least t and the average degree of vertices in each block is at most t/4, then an independent transversal of P exists. We present a construction showing that this result is optimal: for any ε&gt;0 and sufficiently large t, there is a family of forests with vertex partitions whose block size is at least t, average degree of vertices in each block is at most (1/4+ε)t, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.

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/GA20-09525S" target="_blank" >GA20-09525S: Strukturální vlastnosti tříd grafů charakterizovaných zakázanými podgrafy</a><br>

Návaznosti

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

Rok uplatnění

2023

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

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

1097-0118

Svazek periodika

102

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

14

Strana od-do

374-387

Kód UT WoS článku

000841136400001

EID výsledku v databázi Scopus

2-s2.0-85135964681