Buchumschlag

Bounded twin-width graphs are polynomially $χ$-bounded

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bourneuf, Romain, Thomassé, Stéphan
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Discrete Mathematics Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

Sample compression schemes for balls in structurally sparse graphs
von: Bourneuf, Romain, et al.
Veröffentlicht: (2026)

On cuts of small chromatic number in sparse graphs
von: Aubian, Guillaume, et al.
Veröffentlicht: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A structural description of Zykov and Blanche Descartes graphs
von: Marin, Malory, et al.
Veröffentlicht: (2024)

Tree decompositions whose trees are subgraphs: An application of Simon's factorization
von: Bourneuf, Romain, et al.
Veröffentlicht: (2026)

Making Graphs Irregular through Irregularising Walks
von: Bensmail, Julien, et al.
Veröffentlicht: (2025)

$χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
von: Bonamy, Marthe, et al.
Veröffentlicht: (2025)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
von: Baste, Julien, et al.
Veröffentlicht: (2025)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
von: Jedličková, Nikola, et al.
Veröffentlicht: (2023)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
von: Pilipczuk, Marcin, et al.
Veröffentlicht: (2023)

Twin-width and permutations
von: Bonnet, Édouard, et al.
Veröffentlicht: (2021)

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2024)

A polynomial bound for the minimal excluded minors for a surface
von: Houdaigoui, Sarah, et al.
Veröffentlicht: (2026)

Bounding $\varepsilon$-scatter dimension via metric sparsity
von: Bourneuf, Romain, et al.
Veröffentlicht: (2024)

Elimination distance to bounded degree on planar graphs
von: Lindermayr, Alexander, et al.
Veröffentlicht: (2020)

A quasi-polynomial bound for the minimal excluded minors for a surface
von: Houdaigoui, Sarah, et al.
Veröffentlicht: (2025)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Efficient polynomial-time approximation scheme for the genus of dense graphs
von: Jing, Yifan, et al.
Veröffentlicht: (2020)

Strong odd colorings in graph classes of bounded expansion
von: Pilipczuk, Michał
Veröffentlicht: (2025)

Cops and robber in graphs with bounded vertex cover number
von: Bose, Prosenjit, et al.
Veröffentlicht: (2026)

Reuniting $χ$-boundedness with polynomial $χ$-boundedness
von: Chudnovsky, Maria, et al.
Veröffentlicht: (2023)

On expectations and variances in the hard-core model on bounded degree graphs
von: Davies, Ewan, et al.
Veröffentlicht: (2025)

Improved lower bounds on the maximum size of graphs with girth 5
von: Goedgebeur, Jan, et al.
Veröffentlicht: (2025)

A Caro-Wei bound for induced linear forests in graphs
von: Joret, Gwenaël, et al.
Veröffentlicht: (2024)

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
von: Bonnet, Édouard, et al.
Veröffentlicht: (2022)

On $(n,m)$-chromatic numbers of graphs having bounded sparsity parameters
von: Das, Sandip, et al.
Veröffentlicht: (2023)

A quasi-optimal upper bound for induced paths in sparse graphs
von: Couëtoux, Basile, et al.
Veröffentlicht: (2025)

Upper bounds on the average number of colors in the non-equivalent colorings of a graph
von: Hertz, Alain, et al.
Veröffentlicht: (2021)

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
von: Botler, Fábio, et al.
Veröffentlicht: (2025)

An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs
von: Char, Arnab, et al.
Veröffentlicht: (2024)

Cycles of Well-Linked Sets II: an Elementary Bound for the Directed Grid Theorem
von: Hatzel, Meike, et al.
Veröffentlicht: (2026)

Lower Bounds and properties for the average number of colors in the non-equivalent colorings of a graph
von: Hertz, Alain, et al.
Veröffentlicht: (2021)

Twin-width of graphs on surfaces
von: Kráľ, Daniel, et al.
Veröffentlicht: (2023)

Twin-width of sparse random graphs
von: Hendrey, Kevin, et al.
Veröffentlicht: (2023)

Dichromatic Number and Cycle Inversions
von: Charbit, Pierre, et al.
Veröffentlicht: (2024)

$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
von: Chakraborty, Dibyayan
Veröffentlicht: (2025)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
von: Gerke, Stefanie, et al.
Veröffentlicht: (2024)