Cover Image

Note about the complexity of the acyclic orientation with parity constraint problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gravier, Sylvain, Petiteau, Matthieu, Sivignon, Isabelle
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Some polynomial classes for the acyclic orientation with parity constraint problem
by: Gravier, Sylvain, et al.
Published: (2026)

Maker-Breaker is solved in polynomial time on hypergraphs of rank 3
by: Galliot, Florian, et al.
Published: (2022)

An improvement on the bound for the acyclic chromatic index
by: Kirousis, Lefteris, et al.
Published: (2026)

Octal Games on Graphs: The game 0.33 on subdivided stars and bistars
by: Beaudou, Laurent, et al.
Published: (2016)

Orthogonality between acyclic subdigraphs and paths in digraphs
by: Silva, Caroline A. de Paula, et al.
Published: (2026)

Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
by: Pépin, Martin, et al.
Published: (2023)

Partitions of planar (oriented) graphs into a connected acyclic and an independent set
by: Cambie, Stijn, et al.
Published: (2024)

Upper bounds on the average edit distance between two random strings
by: Rosenfeld, Matthieu
Published: (2024)

Generalizations of Ferber-Krivelevich and Gallai Theorems on parity of degrees in induced subgraphs
by: Ai, Jiangdong, et al.
Published: (2025)

Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
by: Soltani, Hossein, et al.
Published: (2018)

An explicit condition for boundedly supermultiplicative subshifts
by: Bui, Vuong, et al.
Published: (2024)

On the inversion number of oriented graphs
by: Bang-Jensen, Jørgen, et al.
Published: (2021)

On acyclic b-chromatic number of cubic graphs
by: Anholcer, Marcin, et al.
Published: (2025)

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

On semi-transitive orientability of circulant graphs
by: Srinivasan, Eshwar, et al.
Published: (2024)

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

On the $(\leq p)$-inversion diameter of oriented graphs
by: Havet, Frédéric, et al.
Published: (2026)

Chemically inspired Erdős-Rényi oriented hypergraphs
by: Garcia-Chung, Angel, et al.
Published: (2023)

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

Neighbour sum distinguishing edge-weightings with local constraints
by: Dailly, Antoine, et al.
Published: (2022)

Regular packing of rooted hyperforests with root constraints in hypergraphs
by: Hoppenot, Pierre, et al.
Published: (2023)

A note on embracing exchange sequences in oriented matroids
by: Bérczi, Kristóf, et al.
Published: (2025)

On the minimum number of arcs in $4$-dicritical oriented graphs
by: Havet, Frédéric, et al.
Published: (2023)

Note on polychromatic coloring of hereditary hypergraph families II
by: Pálvölgyi, Dömötör
Published: (2026)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Some short notes on oriented line graphs and related matrices
by: Antony, Jacob, et al.
Published: (2025)

Characterizing traces of processes defined by precedence and response constraints: an order theory approach
by: Dukes, Mark, et al.
Published: (2023)

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

Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition
by: Ai, Jiangdong, et al.
Published: (2025)

Counting the minimum number of arcs in an oriented graph having weak diameter 2
by: Das, Sandip, et al.
Published: (2023)

Note on the treewidth of graphs excluding a disjoint union of cycles as a minor
by: Joret, Gwenaël, et al.
Published: (2026)

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

The Hajnal--Rothschild problem
by: Frankl, Peter, et al.
Published: (2025)

Odd coloring graphs with linear neighborhood complexity
by: Davies, James, et al.
Published: (2025)

The complexity of computing the period and the exponent of a digraph
by: Kiefer, Stefan, et al.
Published: (2024)

Gathering Information about a Graph by Counting Walks from a Single Vertex
by: Fuhlbrück, Frank, et al.
Published: (2024)

Three aspects of the MSTCI problem
by: Dubinsky, Manuel, et al.
Published: (2023)

Boundary rigidity of finite CAT(0) cube complexes
by: Chalopin, Jérémie, et al.
Published: (2023)

The red-blue-yellow matching problem
by: Aprile, Manuel, et al.
Published: (2026)

The lonely runner conjecture holds for eight runners
by: Rosenfeld, Matthieu
Published: (2025)