The NP-Completeness of Edge-Coloring

Cited in

(only showing first 100 items - show all)

Approximation algorithm for maximum edge coloring
Local edge colouring of Yao-like subgraphs of unit disk graphs
Characterization of a class of graphs related to pairs of disjoint matchings
Achieving maximum chromatic index in multigraphs
On star and caterpillar arboricity
Some results on graphs without long induced paths
Graph coloring with cardinality constraints on the neighborhoods
A combinatorial constraint satisfaction problem dichotomy classification conjecture
Mixed graph edge coloring
Approximating the maximum 3-edge-colorable subgraph problem
On Vizing's bound for the chromatic index of a multigraph
Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
An application of Tutte's theorem to 1-factorization of regular graphs of high degree
Combinatorial analysis (nonnegative matrices, algorithmic problems)
Decomposition by clique separators
The chromatic index of nearly bipartite multigraphs
Intersection graphs of paths in a tree
The strong chromatic number of partial triple systems
Parallel O(log n) time edge-colouring of trees and Halin graphs
The complexity of scheduling independent two-processor tasks on dedicated processors
Edge-colouring random graphs
Edge-packings of graphs and network reliability
Class one graphs
Matching structure and the matching lattice
Applications of edge coloring of multigraphs to vertex coloring of graphs
Two conjectures on edge-colouring
Gallai graphs and anti-Gallai graphs
The ellipsoid method and its consequences in combinatorial optimization
An appraisal of computational complexity for operations researchers
Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
The complexity of controlled selection
NP-completeness of edge-colouring some restricted graphs
A polyhedral approach to edge coloring
Some results concerning the complexity of restricted colorings of graphs
Edge colouring line graphs of unicyclic graphs
Near-optimal, distributed edge colouring via the nibble method
Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings
Edge coloring nearly bipartite graphs
Interval edge coloring of a graph with forbidden colors
Total colouring regular bipartite graphs is NP-hard
How to find overfull subgraphs in graphs with large maximum degree
The hardness of approximation: Gap location
Regular codes in regular graphs are difficult
The probabilistic method yields deterministic parallel algorithms
The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares
Preassignment requirements in chromatic scheduling
Vertex-splitting and chromatic index critical graphs
Tight approximations for resource constrained scheduling and bin packing
Coloring edges of self-complementary graphs
Characterizing and edge-colouring split-indifference graphs
Covering regular graphs
On edge-colouring indifference graphs
Edge ranking of graphs is hard
Decompositions for the edge colouring of reduced indifference graphs.
The complexity of the \(T\)-coloring problem for graphs with small degree
New bounds for optimum traffic assignment in satellite communication.
On the choice number of claw-free perfect graphs
3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
Short solution of Kotzig's problem for bipartite graphs
Linear \(k\)-arboricities on trees
4-edge-coloring graphs of maximum degree 3 in linear time
Routing and path multicoloring
Superposition and constructions of graphs without nowhere-zero k-flows
Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
On claw-free asteroidal triple-free graphs
List-edge-colouring planar graphs with precoloured edges
Algorithmic problems in right-angled Artin groups: complexity and applications
Space-efficient Euler partition and bipartite edge coloring
Trees, paths, stars, caterpillars and spiders
Minimum multiplicity edge coloring via orientation
When patrolmen become corrupted: monitoring a graph using faulty mobile robots
Disconnected g_c-critical graphs
On the complexity of computing MP distance between binary phylogenetic trees
On the \(b\)-continuity of the lexicographic product of graphs
A coloring algorithm for \(4 K_1\)-free line graphs
Shifted matroid optimization
On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
On \(f\)-colorings of nearly bipartite graphs
Graphs with small fall-spectrum
Graph edge coloring: a survey
Independent feedback vertex set for P₅-free graphs
Classifying \(k\)-edge colouring for \(H\)-free graphs
The classification of \(f\)-coloring of graphs with large maximum degree
Chromatic index determined by fractional chromatic index
On the chromatic index of join graphs and triangle-free graphs with large maximum degree
On the algorithmic aspects of strong subcoloring
The P versus NP-complete dichotomy of some challenging problems in graph theory
\(b\)-coloring of tight graphs
Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
Designing optimally multiplexed SNP genotyping assays
New algorithms for maximum disjoint paths based on tree-likeness
How important are branching decisions: fooling MIP solvers
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
On sum coloring of graphs
Efficient algorithms for path partitions
Jump number maximization for proper interval graphs and series-parallel graphs
Edge dominating set and colorings on graphs with fixed clique-width
On edge perfectness and classes of bipartite graphs

This page was built for publication: The NP-Completeness of Edge-Coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3928241)