Imagen de Portada

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bok, Jan, Jedlickova, Nikola, Martin, Barnaby, Ochem, Pascal, Paulusma, Daniel, Smith, Siani
Formato:	Preprint
Publicado:	2020
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

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
por: Lozin, Vadim, et al.
Publicado: (2022)

Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions
por: Bok, Jan, et al.
Publicado: (2025)

Computational complexity of covering regular trees
por: Bok, Jan, et al.
Publicado: (2025)

Colouring Probe $H$-Free Graphs
por: Paulusma, Daniël, et al.
Publicado: (2025)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
por: Bok, Jan, et al.
Publicado: (2021)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
por: Lucke, Felicia, et al.
Publicado: (2024)

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

List homomorphisms to separable signed graphs
por: Bok, Jan, et al.
Publicado: (2023)

On the expressive power of $2$-edge-colourings of graphs
por: Bok, Jan, et al.
Publicado: (2025)

4-tangrams are 4-avoidable
por: Ochem, Pascal, et al.
Publicado: (2025)

Finding d-Cuts in Claw-free Graphs
por: Ahn, Jungho, et al.
Publicado: (2025)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
por: Ahn, Jungho, et al.
Publicado: (2026)

Contact graphs of boxes with unidirectional contacts
por: Gonçalves, Daniel, et al.
Publicado: (2023)

Steiner Forest for $H$-Subgraph-Free Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

Critical exponent of binary words with few distinct palindromes
por: Dvořáková, L'ubomíra, et al.
Publicado: (2023)

Comparing Width Parameters on Graph Classes
por: Brettell, Nick, et al.
Publicado: (2023)

Computing Subset Vertex Covers in $H$-Free Graphs
por: Brettell, Nick, et al.
Publicado: (2023)

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

Finding $d$-Cuts in Probe $H$-Free Graphs
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

Directed Acyclic Outerplanar Graphs Have Constant Stack Number
por: Jungeblut, Paul, et al.
Publicado: (2022)

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

On Modular Edge Colourings of Graphs
por: Berthe, Gaétan, et al.
Publicado: (2025)

3-Colouring Planar Graphs
por: Dujmović, Vida, et al.
Publicado: (2025)

Acyclic colourings of graphs with obstructions
por: Chuet, Quentin, et al.
Publicado: (2022)

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

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
por: Beaudou, Laurent, et al.
Publicado: (2025)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
por: Bonomo-Braberman, Flavia, et al.
Publicado: (2025)

Pseudoperiodic Words and a Question of Shevelev
por: Meleshko, Joseph, et al.
Publicado: (2022)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
por: Lucke, Felicia, et al.
Publicado: (2023)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
por: Johnson, Matthew, et al.
Publicado: (2022)

Colouring t-perfect graphs
por: Chudnovsky, Maria, et al.
Publicado: (2024)

Bounding Width on Graph Classes of Constant Diameter
por: Dabrowski, Konrad K., et al.
Publicado: (2025)

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

Acyclic Edge Coloring of 3-sparse Graphs
por: Anto, Nevil, et al.
Publicado: (2025)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
por: Holtgrefe, Niels, et al.
Publicado: (2024)

Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces
por: Brucker, Francois, et al.
Publicado: (2024)

A Note on the Complexity of Graph Recoloring
por: Bousquet, Nicolas
Publicado: (2024)

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs
por: Bhyravarapu, Sriram, et al.
Publicado: (2021)

Antisquares and Critical Exponents
por: Baranwal, Aseem, et al.
Publicado: (2022)