Cover Image

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_4$-free graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hartel, Thilo, Picasarri-Arrieta, Lucas, Rautenbach, Dieter
Format:	Preprint
Published:	2025
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Degenerate Vertex Cuts in Sparse Graphs
by: Hartel, Thilo, et al.
Published: (2025)

The minimum number of maximal independent sets in graphs with given order and independence number
by: Tian, Yuting, et al.
Published: (2024)

On the minimum number of arcs in $4$-dicritical oriented graphs
by: Havet, Frédéric, et al.
Published: (2023)

The minimum number of maximal independent sets in twin-free graphs
by: Cambie, Stijn, et al.
Published: (2022)

Dichromatic number of chordal graphs
by: Bessy, Stéphane, et al.
Published: (2023)

Acyclic dichromatic number of oriented graphs
by: Bang-Jensen, Jørgen, et al.
Published: (2025)

Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$
by: Picasarri-Arrieta, Lucas, et al.
Published: (2023)

Induced rational exponents and bipartite subgraphs in $K_{s, s}$-free graphs
by: Dong, Zichao, et al.
Published: (2025)

The minimum number of maximal dissociation sets in unicyclic graphs
by: Zhang, Junxia, et al.
Published: (2024)

Largest common subgraph of two forests
by: Rautenbach, Dieter, et al.
Published: (2024)

On cuts of small chromatic number in sparse graphs
by: Aubian, Guillaume, et al.
Published: (2025)

On the minimum number of maximal distance-$k$ independent sets in trees
by: Taletskii, Dmitrii
Published: (2026)

Backbone colouring of chordal graphs
by: Araújo, Júlio, et al.
Published: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
by: Michel, Lukas, et al.
Published: (2024)

Statistics of maximal independent sets in grid-like graphs
by: Axelrod, Levi, et al.
Published: (2025)

Generalized DP-colorings of digraphs
by: Picasarri-Arrieta, Lucas, et al.
Published: (2025)

Complexity results on the decomposition of a digraph into directed linear forests and out-stars
by: Hörsch, Florian, et al.
Published: (2024)

Increasing arc-connectivity by bounded- and fixed-size inversions
by: Hörsch, Florian, et al.
Published: (2026)

Subdivisions in dicritical digraphs with large order or digirth
by: Picasarri-Arrieta, Lucas, et al.
Published: (2024)

Counting independent sets in expanding bipartite regular graphs
by: Collares, Maurício, et al.
Published: (2025)

Independence, induced subgraphs, and domination in $K_{1,r}$-free graphs
by: Caro, Yair, et al.
Published: (2025)

On cubic graphs having the maximal coalition number
by: Dobrynin, Andrey A., et al.
Published: (2024)

Non-bipartite graphs without theta subgraphs
by: Fang, Longfei, et al.
Published: (2025)

Coloring graphs with forbidden almost bipartite subgraphs
by: Anderson, James, et al.
Published: (2022)

A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings
by: Omaña-Pulido, Elsa, et al.
Published: (2025)

Balanced bipartite distance of $K_4$-free graphs
by: Balogh, József, et al.
Published: (2026)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

An analogue of Reed's conjecture for digraphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

The 3-dicritical semi-complete digraphs
by: Havet, Frédéric, et al.
Published: (2024)

The density of maximal IC-plane graphs and maximal NIC-plane graphs
by: Ding, Zongpeng, et al.
Published: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

On the number of edges in saturated partial embeddings of maximal planar graphs
by: Barát, János, et al.
Published: (2025)

Chromatic discrepancy of locally $s$-colourable graphs
by: Corsini, Timothée, et al.
Published: (2025)

Unavoidable induced subgraphs in graphs with complete bipartite induced minors
by: Chudnovsky, Maria, et al.
Published: (2024)

The minimum size of maximal bipartite IC-plane graphs with given connectivity
by: Wang, Guiping, et al.
Published: (2025)

Dense minors and bipartite independence numbers
by: Wang, Xia, et al.
Published: (2025)

Maximum $k$-colourable induced subgraphs in $(P_5+rK_1)$-free graphs
by: Henderson, Cicely, et al.
Published: (2024)

Edge-colouring and orientations: applications to degree- and $χ$-boundedness
by: Char, Arnab, et al.
Published: (2025)

A simple proof of the existence of complete bipartite graph immersion in graphs with independence number two
by: Chen, Rong, et al.
Published: (2024)

Redicolouring digraphs: directed treewidth and cycle-degeneracy
by: Nisse, Nicolas, et al.
Published: (2023)