The NP-Completeness of Edge-Coloring

Cited in

(only showing first 100 items - show all)

On excessive index of certain networks
Parameterized complexity of max-lifetime target coverage in wireless sensor networks
Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
Simple reduction of f-colorings to edge-colorings
On the parameterized complexity of coloring graphs in the absence of a linear forest
The satisfactory partition problem
Linear \(k\)-arboricities on trees
On the chromatic edge stability index of graphs
Acyclic coloring of products of digraphs
Complexity of graph covering problems
On edge-colouring indifference graphs
On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs
On the chromatic index of join graphs and triangle-free graphs with large maximum degree
Fractal networks: topology, dimension, and complexity
\(H\)-colouring \(P_t\)-free graphs in subexponential time
Edge-chromatic numbers of Mycielski graphs
A comparison of two edge-coloring formulations
Algorithms and almost tight results for 3-colorability of small diameter graphs
Jump number maximization for proper interval graphs and series-parallel graphs
Some graphs of class 1 for \(f\)-colorings
The probabilistic method yields deterministic parallel algorithms
Coloring problems on bipartite graphs of small diameter
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
Near-optimal, distributed edge colouring via the nibble method
Coloring vertices of claw-free graphs in three colors
The 2nd-order conditional 3-coloring of claw-free graphs
Coloring graphs without short cycles and long induced paths
On disjoint matchings in cubic graphs
Colouring vertices of triangle-free graphs without forests
The Fan-Raspaud conjecture: a randomized algorithmic approach and application to the pair assignment problem in cubic networks
A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree
4-edge-coloring graphs of maximum degree 3 in linear time
Routing and path multicoloring
Colouring square-free graphs without long induced paths
The complexity of LSH feasibility
Tight approximations for resource constrained scheduling and bin packing
Chromatic index determined by fractional chromatic index
The chromatic index of nearly bipartite multigraphs
Exploring the complexity boundary between coloring and list-coloring
Graphs whose edge set can be partitioned into maximum matchings
Morphology of small snarks
The complexity of the zero-sum 3-flows
NP-completeness of edge-colouring some restricted graphs
Characterization of a class of graphs related to pairs of disjoint matchings
Improved edge-coloring with three colors
Chromatic Gallai identities operating on Lovász number
Edge covering coloring of nearly bipartite graphs
f-class two graphs whose f-cores have maximum degree two
A parallel algorithm for edge-coloring partial k-trees
scientific article; zbMATH DE number 7525468 (Why is no real title available?)
Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
The palette index of Sierpiński triangle graphs and Sierpiński graphs
Coloring graphs without short cycles and long induced paths
Injective edge coloring of graphs
Circuit double covers of graphs
Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
Superposition of snarks revisited
Edge-colouring random graphs
The complexity of arc-colorings for directed hypergraphs
COLORING ALGORITHMS ON SUBCUBIC GRAPHS
New bounds for optimum traffic assignment in satellite communication.
Independent feedback vertex set for \(P_5\)-free graphs
Densities, matchings, and fractional edge-colorings
The Hilton-Zhao conjecture is true for graphs with maximum degree 4
Minimizing total completion time in multiprocessor job systems with energy constraint
Characterizing and edge-colouring split-indifference graphs
Decompositions for the edge colouring of reduced indifference graphs.
Edge-coloring of 3-uniform hypergraphs
Edge-colouring of joins of regular graphs. I
A survey on the computational complexity of coloring graphs with forbidden subgraphs
Domination, coloring and stability in \(P_5\)-reducible graphs
On claw-free asteroidal triple-free graphs
Deciding whether four perfect matchings can cover the edges of a snark is NP-complete
Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
Edge-colouring graphs with bounded local degree sums
scientific article; zbMATH DE number 7656024 (Why is no real title available?)
Interval edge coloring of a graph with forbidden colors
List-edge-colouring planar graphs with precoloured edges
Near-optimal distributed edge coloring
The complexity of path coloring and call scheduling
Colouring H-free graphs of bounded diameter.
Total chromatic number of unichord-free graphs
Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
Edge coloring nearly bipartite graphs
An upper bound for the choice number of star edge coloring of graphs
Minimum decomposition into convex binary matrices
3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
Colorings with few colors: counting, enumeration and combinatorial bounds
Determining the circular flow number of a cubic graph
On multiples of simple graphs and Vizing's theorem
Colouring simplicial complexes via the Lechuga-Murillo's model
The complexity of counting edge colorings for simple graphs
Decomposition by clique separators
Intersection graphs of paths in a tree
Efficient algorithms for path partitions
A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
On \(g_c\)-colorings of nearly bipartite graphs.
scientific article; zbMATH DE number 7790331 (Why is no real title available?)
Algorithms for finding f-colorings of partial k-trees

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)