NP completeness of the edge precoloring extension problem on bipartite graphs
From MaRDI portal
Publication:4406072
DOI10.1002/jgt.10088zbMath1026.68065OpenAlexW4241291398MaRDI QIDQ4406072
Publication date: 25 June 2003
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.10088
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Avoiding and extending partial edge colorings of hypercubes ⋮ Approximate constrained bipartite edge coloring ⋮ List covering of regular multigraphs ⋮ Restricted extension of sparse partial edge colorings of complete graphs ⋮ Extending partial representations of interval graphs ⋮ Time slot scheduling of compatible jobs ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ Flexibility of triangle‐free planar graphs ⋮ List covering of regular multigraphs with semi-edges ⋮ Restricted extension of sparse partial edge colorings of hypercubes ⋮ Complexity of Locally Injective Homomorphism to the Theta Graphs ⋮ Extending upward planar graph drawings ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ On the computational complexity of partial covers of theta graphs ⋮ Edge-coloring of 3-uniform hypergraphs ⋮ The hardness of train rearrangements ⋮ On avoiding some families of arrays ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Restricted cycle factors and arc-decompositions of digraphs
Cites Work
