Cover Image

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Mkrtchyan, Vahan
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics 05C85, 68R10, 05C15, 05C70
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
by: Furmańczyk, Hanna, et al.
Published: (2020)

Three results towards the approximation of special maximum matchings in graphs
by: Mkrtchyan, Vahan
Published: (2024)

Non-conflicting no-where zero $Z_2\times Z_2$ flows in cubic graphs
by: Mkrtchyan, Vahan
Published: (2024)

Expanding vertices to triangles in cubic graphs
by: Mazzuoccolo, Giuseppe, et al.
Published: (2025)

Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
by: Inoue, Yuta, et al.
Published: (2024)

Improved bounds for acyclic coloring parameters
by: Kirousis, Lefteris, et al.
Published: (2022)

Infinite families of planar graphs of a given injective chromatic number
by: Daneels, Matias, et al.
Published: (2024)

On z-coloring and ${\rm b}^{\ast}$-coloring of graphs as improved variants of the b-coloring
by: Zaker, Manouchehr
Published: (2024)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

Small-scale operations on graphic sequences
by: Rusu, Irena
Published: (2026)

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

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
by: Gollin, J. Pascal, et al.
Published: (2023)

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

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

Large induced subgraph with a given pathwidth in outerplanar graphs
by: Matsumoto, Naoki, et al.
Published: (2025)

Fractional list packing for layered graphs
by: Cambie, Stijn, et al.
Published: (2024)

Edge open packing: complexity, algorithmic aspects, and bounds
by: Brešar, Boštjan, et al.
Published: (2024)

Dirac's theorem and the switch geometry of perfect matchings
by: Kang, Ross J., et al.
Published: (2026)

Improper coloring of toroidal graphs
by: Kolačkovská, Alexandra, et al.
Published: (2025)

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

Towards Characterization of 5-List-Colorability of Toroidal Graphs
by: Dvořák, Zdeněk, et al.
Published: (2024)

Circular-arc H-graphs: Ordering Characterizations and Forbidden Patterns
by: Paul, Indrajit, et al.
Published: (2025)

Odd coloring of 2-boundary planar graphs and beyond
by: Liu, Weichan, et al.
Published: (2022)

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

More relations between $λ$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
by: Zaker, Manouchehr
Published: (2021)

On the structure of (dart, odd hole)-free graphs
by: Hoàng, Chính T.
Published: (2025)

$\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth
by: Zaker, Manouchehr
Published: (2024)

Computational methods for finding bi-regular cages
by: Goedgebeur, Jan, et al.
Published: (2024)

Maximizing the number of integer pairs summing to powers of 2 via graph labeling and solving restricted systems of linear (in)equations
by: Alekseyev, Max A.
Published: (2023)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
by: Paul, Christophe, et al.
Published: (2024)

The Local Structure Theorem for Graph Minors with finite index
by: Paul, Christophe, et al.
Published: (2025)

Unavoidable induced subgraphs in graphs with complete bipartite induced minors
by: Chudnovsky, Maria, et al.
Published: (2024)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

A greedy heuristic for graph burning
by: García-Díaz, Jesús, et al.
Published: (2024)

Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture
by: Inoue, Yuta, et al.
Published: (2025)

Symmetric Domino Tilings of Aztec Diamonds
by: Paul, Pravakar, 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)

Computing the permanental polynomial of $4k$-intercyclic bipartite graphs
by: Bapat, Ravindra B., et al.
Published: (2024)

Zero blocking numbers of graphs with complexity results
by: Lin, Hau-Yi, et al.
Published: (2025)