Graph Tilings in Incompatibility Systems

DOI10.1137/22M1506353zbMATH Open1521.05159arXiv2207.05386OpenAlexW4386255082MaRDI QIDQ6046822FDOQ6046822

Authors: Jie Hu, Hao Li, Donglei Yang 

Publication date: 6 September 2023

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

Abstract: An emph{incompatibility system} $(G,mathcalF)$ consists of a graph $G$ and a family $mathcalF={F_v}_{vinV(G)}$ over $G$ with $F_{v}subseteqe,e^{\prime }inE(G)choose2:ecap{e}^{\prime }=v$. We say that two edges $e,e^{\prime }inE(G)$ are emph{incompatible} if $e,e^{\prime }in{F}_v$ for some $vinV(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,mathcalF)$ is emph{$Delta$-bounded} if for any vertex $v$ and any edge $e$ incident with $v$, there are at most $Delta$ 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 $alpha>0$ and any graph $H$ with $h$ vertices, there exists a constant $mu>0$ such that for any sufficiently large $n$ with $ninhmathbbN$, if $G$ is an $n$-vertex graph with $delta(G)ge(1-frac1ch{i}^{\ast }(H)+alpha)n$ and $(G,mathcalF)$ is a $mun$-bounded incompatibility system, then there exists a compatible $H$-factor in $G$, where the value $ch{i}^{\ast }(H)$ is either the chromatic number $chi(H)$ or the critical chromatic number $ch{i}_{cr}(H)$ and we provide a dichotomy as in the K"{u}hn--Osthus result. Moreover, we give examples $H$ for which there exists an $mun$-bounded incompatibility system $(G,mathcalF)$ with $ninhmathbbN$ and $delta(G)ge(1-frac1ch{i}^{\ast }(H)+fracmu2)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.

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

Recommendations

• Tilings in graphons
• scientific article; zbMATH DE number 5139439
• Tilings in vertex ordered graphs
• Tilings from graph directed iterated function systems
• Tilings in randomly perturbed dense graphs
• Bipartite graph tiling
• Incomparability graphs of lattices
• Tiling problems, automata, and tiling graphs
• A note on bipartite graph tiling
• Note on bipartite graph tilings

zbMATH Keywords

robustnessgraph tilingsincompatibility system

Mathematics Subject Classification ID

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

Cites Work

• Tiling Turán theorems
• \(H\)-factors in dense graphs
• The minimum degree threshold for perfect graph packings
• Spanning trees in random graphs
• \(F\)-factors in hypergraphs via absorption
• An Ore-type theorem for perfect packings in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proof of the Alon-Yuster conjecture
• Rainbow matchings in Dirac bipartite graphs
• Some Theorems on Abstract Graphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Blow-up lemma
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Biased Positional Games
• On the resilience of long cycles in random graphs
• Local resilience of almost spanning trees in random graphs
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Local resilience of graphs
• Title not available (Why is that?)
• Lopsided Lovász Local lemma and Latin transversals
• Biased positional games and small hypergraphs with large covers
• Resilient pancyclicity of random and pseudorandom graphs
• Perfect packings with complete graphs minus an edge
• Proof of a tiling conjecture of Komlós
• K₄⁻‐factor in a graph
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Title not available (Why is that?)
• Increasing the chromatic number of a random graph
• Alternating Hamiltonian cycles
• A property of the colored complete graph
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Compatible Hamilton cycles in random graphs
• Title not available (Why is that?)
• Robust Hamiltonicity of Dirac graphs
• Compatible Hamilton cycles in Dirac graphs
• Robustness of graph properties
• Rainbow \(H\)-factors
• A rainbow Dirac's theorem
• Title not available (Why is that?)
• Embedding rainbow trees with applications to graph labelling and decomposition
• Rainbow factors in hypergraphs
• Rainbow structures in locally bounded colorings of graphs
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• A degree sequence version of the Kühn-Osthus tiling theorem
• A rainbow blow-up lemma
• Title not available (Why is that?)
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• Factors in randomly perturbed hypergraphs

Cited In (3)

• A Ramsey–Turán theory for tilings in graphs
• Compatible powers of Hamilton cycles in dense graphs
• Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs

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)