Graph Tilings in Incompatibility Systems

DOI10.1137/22M1506353MaRDI QIDQ6046822zbMATH OpenOpenAlexFDO

Publication date 6 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.05386

robustness graph tilings incompatibility system

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An emph{incompatibility system}

(G, m a t h c a l F)

consists of a graph

G

and a family

m a t h c a l F = {F_{v}}_{v i n V (G)}

over

G

with

F_{v} s u b s e t e q e, e^{'} i n E (G) c h o o s e 2 : e c a p e^{'} = v

. We say that two edges

e, e^{'} i n E (G)

are emph{incompatible} if

e, e^{'} i n F_{v}

for some

v i n V (G)

, and otherwise emph{compatible}. A subgraph

H

of

G

is emph{compatible} if every pair of edges in

H

are compatible. An incompatibility system

(G, m a t h c a l F)

is emph{

D e l t a

-bounded} if for any vertex

v

and any edge

e

incident with

v

, there are at most

D e l t a

members of

F_{v}

containing

e

. This notion was partly motivated by a concept of transition system introduced by Kotzig in 1968, and first formulated by Krivelevich, Lee and Sudakov to study the robustness of Hamiltonicity of Dirac graphs. We prove that for any

a l p h a > 0

and any graph

H

with

h

vertices, there exists a constant

m u > 0

such that for any sufficiently large

n

with

n i n h m a t h b b N

, if

G

is an

n

-vertex graph with

d e l t a (G) g e (1 - f r a c 1 c h i^{*} (H) + a l p h a) n

and

(G, m a t h c a l F)

is a

m u n

-bounded incompatibility system, then there exists a compatible

H

-factor in

G

, where the value

c h i^{*} (H)

is either the chromatic number

c h i (H)

or the critical chromatic number

c h i_{c r} (H)

and we provide a dichotomy as in the K"{u}hn--Osthus result. Moreover, we give examples

H

for which there exists an

m u n

-bounded incompatibility system

(G, m a t h c a l F)

with

n i n h m a t h b b N

and

d e l t a (G) g e (1 - f r a c 1 c h i^{*} (H) + f r a c m u 2) n

such that

G

contains no compatible

H

-factor. Unlike in the previous work of K"{u}hn and Osthus on embedding

H

-factors, our proof uses the lattice-based absorption method.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Graph Tilings in Incompatibility Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046822)