Cover Image

Colouring $(P_r+P_s)$-Free Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Klimošová, Tereza, Malík, Josef, Masařík, Tomáš, Novotná, Jana, Paulusma, Daniël, Slívová, Veronika
Format:	Preprint
Published:	2018
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
by: Kratochvíl, Jan, et al.
Published: (2020)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
by: Jelínek, Vít, et al.
Published: (2020)

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

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

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

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

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

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

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

On Detecting $H$-Induced Minors for Small $H$
by: Eagling-Vose, Tala, et al.
Published: (2026)

Solving Problems on Generalized Convex Graphs via Mim-Width
by: Bonomo-Braberman, Flavia, et al.
Published: (2020)

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

Graph Classes Closed under Self-intersection
by: Dabrowski, Konrad K., et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

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

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

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

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
by: Benedek, Márton, et al.
Published: (2023)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
by: Masařík, Tomáš, et al.
Published: (2025)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

The Parameterized Landscape of Labeled Graph Contractions
by: Lafond, Manuel, et al.
Published: (2025)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)