Imagen de Portada

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bourneuf, Romain, Charbit, Pierre, Thomassé, Stéphan
Formato:	Preprint
Publicado:	2025
Materias:	Discrete Mathematics Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Bounded twin-width graphs are polynomially $χ$-bounded
por: Bourneuf, Romain, et al.
Publicado: (2023)

Dichromatic Number and Cycle Inversions
por: Charbit, Pierre, et al.
Publicado: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
por: Bourneuf, Romain, et al.
Publicado: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
por: Bourneuf, Romain, et al.
Publicado: (2025)

Sample compression schemes for balls in structurally sparse graphs
por: Bourneuf, Romain, et al.
Publicado: (2026)

Making Graphs Irregular through Irregularising Walks
por: Bensmail, Julien, et al.
Publicado: (2025)

Tree decompositions whose trees are subgraphs: An application of Simon's factorization
por: Bourneuf, Romain, et al.
Publicado: (2026)

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

The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number
por: Goetze, Miriam, et al.
Publicado: (2025)

Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
por: Schneider, Samuel, et al.
Publicado: (2025)

A structural description of Zykov and Blanche Descartes graphs
por: Marin, Malory, et al.
Publicado: (2024)

On the Complexity of Hop Domination and 2-Step Domination in Graph Classes
por: Das, Sandip, et al.
Publicado: (2026)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
por: Charbit, Pierre, et al.
Publicado: (2025)

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
por: Gamarnik, David, et al.
Publicado: (2023)

Paired Disjunctive Domination Number of Middle Graphs
por: Golpek, Hande Tuncel, et al.
Publicado: (2025)

The Packing Chromatic Number of the Infinite Square Grid is 15
por: Subercaseaux, Bernardo, et al.
Publicado: (2023)

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

On the Modular Chromatic Index of Random Hypergraphs
por: Carenini, Gaia, et al.
Publicado: (2025)

Fractional Chromatic Numbers from Exact Decision Diagrams
por: Brand, Timo, et al.
Publicado: (2024)

Upper Bounds on the Acyclic Chromatic Index of Degenerate Graphs
por: Anto, Nevil, et al.
Publicado: (2023)

Neighborhood complexity of planar graphs
por: Joret, Gwenaël, et al.
Publicado: (2023)

Graphs With the Same Edge Count in Each Neighborhood
por: Sheffield, Nathan S., et al.
Publicado: (2025)

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

The Chromatic Number of Kneser Hypergraphs via Consensus Division
por: Haviv, Ishay
Publicado: (2023)

Twin-width and permutations
por: Bonnet, Édouard, et al.
Publicado: (2021)

Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
por: Botler, F., et al.
Publicado: (2024)

Minimum Eccentric Connectivity Index for Graphs with Fixed Order and Fixed Number of Pending Vertices
por: Devillez, Gauvain, et al.
Publicado: (2018)

The Normal Play of the Domination Game
por: Brito, João Marcos, et al.
Publicado: (2025)

The Dominating 4-Colour Theorem
por: Girão, António, et al.
Publicado: (2026)

Connected Dominating Sets in Triangulations
por: Bose, Prosenjit, et al.
Publicado: (2023)

The Normal Domination Partizan Game in Stars
por: Sampaio, Rudini, et al.
Publicado: (2026)

On Tuza's Conjecture in Dense Graphs
por: Chahua, Luis, et al.
Publicado: (2024)

Face-hitting Dominating Sets in Planar Graphs
por: Francis, P., et al.
Publicado: (2024)

Structural Parameters for Dense Temporal Graphs
por: Enright, Jessica, et al.
Publicado: (2024)

Efficient $k$-limited Dominating Broadcasts in Product Graphs
por: Bharadwaj, et al.
Publicado: (2025)

A Survey on Ordered Ramsey Numbers
por: Balko, Martin
Publicado: (2025)

A Demigod's Number for the Rubik's Cube
por: Merino, Arturo, et al.
Publicado: (2024)

Exploring Algorithmic Solutions for the Independent Roman Domination Problem in Graphs
por: Paul, Kaustav, et al.
Publicado: (2024)

Complexity Issues Concerning the Quadruple Roman Domination Problem in Graphs
por: Palagiri, V. S. R., et al.
Publicado: (2024)

Basis Number and Pathwidth
por: Miraftab, Babak, et al.
Publicado: (2026)