Cover Image

Edge-coloring problems with forbidden patterns and planted colors

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barsukov, Alexey, Mottet, Antoine, Perinti, Davide
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics 68R10 (Primary) 03B70, 05C15, 05C55, 08A70 (Secondary) F.2.2; G.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
by: Mkrtchyan, Vahan
Published: (2024)

On the Number of Vertices/Edges whose Deletion Preserves the Konig-Egervary Property
by: Levit, Vadim E., et al.
Published: (2024)

On corona of Konig-Egervary graphs
by: Levit, Vadim E., et al.
Published: (2024)

Almost Bipartite non-König-Egerváry Graphs Revisited
by: Levit, Vadim E., et al.
Published: (2024)

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

W-state graphs: Structure and Algorithms
by: Gajjala, Rishikesh, et al.
Published: (2026)

On the complexity of Sandwich Problems for $M$-partitions
by: Barsukov, Alexey, et al.
Published: (2026)

The family of all local maximum independent sets is an augmentoid
by: Levit, Vadim E., et al.
Published: (2026)

Gallai's Path Decomposition for 2-degenerate Graphs
by: Anto, Nevil, et al.
Published: (2022)

Computing the forcing spectrum of outerplanar graphs in polynomial time
by: Gorsky, Maximilian, et al.
Published: (2024)

On Edge-Disjoint Maximal Outerplanar Graphs
by: Okada, Yuto, et al.
Published: (2026)

GMSNP and Finite Structures
by: Guzmán-Pro, Santiago
Published: (2024)

The classification of minimally unsatisfiable 2-CNFs -- a fundamental study
by: Abbasizanjani, Hoda, et al.
Published: (2020)

Graphs with core(G) = nucleus(G)
by: Levit, Vadim E., et al.
Published: (2026)

Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
by: Benevides, Fabrício Siqueira, et al.
Published: (2024)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
by: Liang, Kai
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Sparsification of Phylogenetic Covariance Matrices of $k$-Regular Trees
by: Svihla, Sean P., et al.
Published: (2024)

A note on the structure of locally finite planar quasi-transitive graphs
by: Giocanti, Ugo
Published: (2024)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

On 1-Konig-Egervary Graphs
by: Levit, Vadim E., et al.
Published: (2023)

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

Catching Rats in $H$-minor-free Graphs
by: Gorsky, Maximilian, et al.
Published: (2025)

Adjacent vertex distinguishing total coloring of 3-degenerate graphs
by: Behera, Diptimaya, et al.
Published: (2025)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

Backbone coloring for graphs with degree 4
by: Michalik, Krzysztof, et al.
Published: (2024)

Counting Kernels in Directed Graphs with Arbitrary Orientations
by: Jartoux, Bruno
Published: (2022)

Dominic Welsh: his work and influence
by: Farr, Graham, et al.
Published: (2024)

Symmetric Domino Tilings of Aztec Diamonds
by: Paul, Pravakar, et al.
Published: (2024)

Quickly excluding an annotated planar graph
by: Gorsky, Maximilian, et al.
Published: (2026)

The price of homogeneity is polynomial
by: Gorsky, Maximilian, et al.
Published: (2026)

Census Dual Graphs: Properties and Random Graph Models
by: Anderson, Sara, et al.
Published: (2026)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

How Local Separators Shape Community Structure in Large Networks
by: Frenkel, Sarah, et al.
Published: (2025)

Packing coloring of hypercubes with extended Hamming codes
by: Gregor, Petr, et al.
Published: (2023)

Separating Matchings in Cubic Graphs
by: Gutiérrez, Juan, et al.
Published: (2026)

Directed branch-width: A directed analogue of tree-width
by: Bumpus, Benjamin Merlin, et al.
Published: (2020)

Hamiltonian laceability with a set of faulty edges in hypercubes
by: Ali, Abid, et al.
Published: (2025)