Cover Image

The Complexity of Color-constrained Paths in Semicomplete Multipartite Digraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Brinkmann, Julian
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Digraph Branchings and Matrix Determinants
by: Ghosh, Sayani, et al.
Published: (2023)

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
by: Ai, Jiangdong, et al.
Published: (2024)

Boundary vertices of Strongly Connected Digraphs with respect to `Sum Metric'
by: Anand, Bijo S., et al.
Published: (2025)

Coloring Grids Avoiding Bicolored Paths
by: Keskinkilic, Derman, et al.
Published: (2023)

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

Towards Transitive-free Digraphs
by: Abhinav, Ankit, et al.
Published: (2025)

Star colouring and locally constrained graph homomorphisms
by: Antony, Cyriac, et al.
Published: (2023)

Path degeneracy and applications
by: Lin, Y., et al.
Published: (2025)

Progressive and Rushed Dyck Paths
by: Bacher, Axel
Published: (2024)

Bounds on Path Energy of Graphs
by: Narke, Amol P., et al.
Published: (2022)

Sublinear Longest Path Transversals
by: Long Jr., James A., et al.
Published: (2020)

On Separating Path and Tree Systems in Graphs
by: Biniaz, Ahmad, et al.
Published: (2023)

Menger's Theorem for Temporal Paths (Not Walks)
by: Ibiapina, Allen, et al.
Published: (2022)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

Covering Complete Geometric Graphs by Monotone Paths
by: Dumitrescu, Adrian, et al.
Published: (2025)

Counting Colored Tilings on Grids and Graphs
by: Ramírez, José L., et al.
Published: (2024)

Coloring bridge-free antiprismatic graphs
by: Robin, Cléophée, et al.
Published: (2024)

Vertex-Based Localization of Erdős-Gallai Theorems for Paths and Cycles
by: Adak, Rajat, et al.
Published: (2025)

A Note on Polychromatic Colorings of Shift-Chains
by: Ueckerdt, Torsten
Published: (2024)

Further Results and Questions on $S$-Packing Coloring of Subcubic Graphs
by: Mortada, Maidoun, et al.
Published: (2024)

The Graph Coloring Game on $4\times n$-Grids
by: Brosse, Caroline, et al.
Published: (2024)

On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs
by: Sanghi, Aryan, et al.
Published: (2026)

Path eccentricity of $k$-AT-free graphs and application on graphs with the consecutive ones property
by: Bastide, Paul, et al.
Published: (2024)

Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two
by: Gerke, S., et al.
Published: (2026)

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

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

A Note on the Complexity of Graph Recoloring
by: Bousquet, Nicolas
Published: (2024)

On the Identity and Group Problems for Complex Heisenberg Matrices
by: Bell, Paul C., et al.
Published: (2023)

$χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

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

Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
by: Goetze, Miriam, et al.
Published: (2024)

Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
by: Burke, Kyle, et al.
Published: (2024)

Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments
by: Spirkl, Sophie, et al.
Published: (2026)

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

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

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
by: Bok, Jan, et al.
Published: (2020)

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

Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity
by: Dong, Sally, et al.
Published: (2023)

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

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)