Cover Image

Improved lower bounds for the maximum order of an induced acyclic subgraph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Asgarli, Shamil, Falkenhagen, Donald, Hoshi, Kaya
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Primary 05C69, Secondary 05C20, 05C85, 05D40
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Coloring graphs as complete graph invariants
by: Asgarli, Shamil, et al.
Published: (2025)

Maximal independent sets in the middle two layers of the Boolean lattice
by: Balogh, József, et al.
Published: (2025)

Distinct degrees and homogeneous sets II
by: Long, Eoin, et al.
Published: (2024)

Cofinality of Regular Tournaments
by: Hatem, Omar, et al.
Published: (2026)

Induced Minor Models. I. Structural Properties and Algorithmic Consequences
by: Bousquet, Nicolas, et al.
Published: (2024)

Excluding an induced wheel minor in graphs without large induced stars
by: Choi, Mujin, et al.
Published: (2025)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
by: Milanič, Martin, et al.
Published: (2024)

Triangle-free triple systems
by: Frankl, Peter, et al.
Published: (2024)

When all directed cycles have the same weight
by: Berger, Eli, et al.
Published: (2026)

Awesome graph parameters
by: Štorgel, Kenny Bešter, et al.
Published: (2025)

Conformality of Minimal Transversals of Maximal Cliques
by: Boros, Endre, et al.
Published: (2024)

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
by: Dallard, Clément, et al.
Published: (2024)

Defective chromatic polynomials
by: Asgarli, Shamil, et al.
Published: (2026)

Chromatic quasisymmetric functions of the path graph
by: Aliniaeifard, Farid, et al.
Published: (2024)

Domination on Vertex-weighted Graphs Induce by a Coloring
by: Garrido-Vizuete, María A., et al.
Published: (2025)

Kernels in digraphs with colored vertices
by: Guevara, Mucuy-kak, et al.
Published: (2025)

Explicit geometric construction of Ramsey graphs
by: Kocbek, Matija
Published: (2025)

Extremal diameters of 3-coloring graphs of trees
by: Asgarli, Shamil, et al.
Published: (2025)

A dual view of Roman Domination: The 2-limited packing problem
by: Bachtler, Oliver, et al.
Published: (2026)

Bell coloring graphs: realizability and reconstruction
by: Asgarli, Shamil, et al.
Published: (2025)

On irreversible spread of influence in edge-weighted graphs
by: Zaker, Manouchehr
Published: (2019)

The intersection density of cubic arc-transitive graphs with $2$-arc-regular full automorphism group equal to $\operatorname{PGL}_2(q)$
by: Meagher, Karen, et al.
Published: (2025)

Sharp bounds for covering with large cliques and independent sets
by: Bitonti, Veronica, et al.
Published: (2026)

Treewidth versus clique number: induced minors
by: Hilaire, Claire, et al.
Published: (2024)

$k$-Fair Coalitions in Graphs
by: Jafari, Abbas, et al.
Published: (2025)

The integer $\{2\}$-domination number of grids
by: Lee, Jia-Ying, et al.
Published: (2025)

Distribution of independent sets in perfect $r$-ary trees
by: Iľkovič, Daniel, et al.
Published: (2026)

Roman $\{2\}$-domination on Graphs with "few" 4-paths
by: Fernández, Lara, et al.
Published: (2025)

Computing the Exchange Number in Graphs with respect to Cycle Convexity
by: Nair, Revathy S., et al.
Published: (2026)

Complexity and Structural Results for the Hull and Convexity Numbers in Cycle Convexity for Graph Products
by: Anand, Bijo S., et al.
Published: (2024)

Mutual k-Visibility in Graphs
by: B, Tonny K, et al.
Published: (2026)

Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs
by: Diamond, Harvey, et al.
Published: (2024)

Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs
by: Diamond, Harvey, et al.
Published: (2024)

Number of independent transversals in multipartite graphs
by: Tang, Yantao, et al.
Published: (2025)

The maximum number of connected sets in regular graphs
by: Cambie, Stijn, et al.
Published: (2023)

The sharp upper bounds on the maximum degree and vertex-connectivity of claw-free 1-planar graphs
by: Zhang, Licheng, et al.
Published: (2025)

Recolouring Homomorphisms to triangle-free reflexive graphs
by: Lee, Jae-baek, et al.
Published: (2021)

Towards a dichotomy for the switch list homomorphism problem for signed graphs
by: Kim, Hyobin, et al.
Published: (2021)

5-Coloring Planar Graphs with a Color Class of Order at Most $|V|/6$
by: Inoue, Yuta, et al.
Published: (2025)

Cup Stacking in Graphs
by: Fay, Paul, et al.
Published: (2023)