The NP-Completeness of Edge-Coloring
From MaRDI portal
Publication:3928241
DOI10.1137/0210055zbMath0473.68034DBLPjournals/siamcomp/Holyer81aOpenAlexW2102669784WikidataQ29013951 ScholiaQ29013951MaRDI QIDQ3928241
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/37c92599655b9f66850f1e4e0e48ad045abad8f6
Related Items (only showing first 100 items - show all)
The chromatic index of nearly bipartite multigraphs ⋮ Intersection graphs of paths in a tree ⋮ A note on optical routing on trees ⋮ Coloring problems on bipartite graphs of small diameter ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Improving a family of approximation algorithms to edge color multigraphs ⋮ Improved edge-coloring with three colors ⋮ On a limit of the method of Tashkinov trees for edge-colouring ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ Edge-colouring of joins of regular graphs. I ⋮ The tournament scheduling problem with absences ⋮ The strong chromatic number of partial triple systems ⋮ A faster test for 4-flow-criticality in snarks ⋮ On the chromatic index of cographs and join graphs ⋮ Edge covering coloring of nearly bipartite graphs ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Complexity of coloring graphs without paths and cycles ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Excessive factorizations of bipartite multigraphs ⋮ Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface ⋮ Computing clique and chromatic number of circular-perfect graphs in polynomial time ⋮ On the complexity of adjacent resource scheduling ⋮ Time slot scheduling of compatible jobs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Algorithmic complexity of proper labeling problems ⋮ On excessive index of certain networks ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ On the max-weight edge coloring problem ⋮ Edge-chromatic numbers of Mycielski graphs ⋮ Injective colorings with arithmetic constraints ⋮ Computational complexity of covering three-vertex multigraphs ⋮ Three ways to cover a graph ⋮ Approximating the chromatic index of multigraphs ⋮ Minimum decomposition into convex binary matrices ⋮ The edge chromatic number of outer-1-planar graphs ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ Determining the total colouring number is NP-hard ⋮ The chromatic index of multigraphs that are nearly full ⋮ Local algorithms for edge colorings in UDGs ⋮ Some criteria for a graph to be class 1 ⋮ Total chromatic number of unichord-free graphs ⋮ Relating edge-coverings to the classification of \(\mathbb Z^k_2\)-magic graphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Randomly colouring graphs (a combinatorial view) ⋮ The 2nd-order conditional 3-coloring of claw-free graphs ⋮ On upper bounds for parameters related to the construction of special maximum matchings ⋮ The complexity of the zero-sum 3-flows ⋮ Measures of edge-uncolorability of cubic graphs ⋮ Excessive index for mesh derived networks ⋮ On the equivalence covering number of splitgraphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Successive partition of edges of bipartite graph into matchings ⋮ An introduction to the discharging method via graph coloring ⋮ On complexity of special maximum matchings constructing ⋮ Critical hereditary graph classes: a survey ⋮ Stable sets versus independent sets ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ A comparison of two edge-coloring formulations ⋮ \([r,s,t\)-coloring of trees and bipartite graphs] ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ Approximating the maximum 2- and 3-edge-colorable subgraph problems ⋮ Interval edge-colorings of complete graphs and \(n\)-dimensional cubes ⋮ On disjoint matchings in cubic graphs ⋮ Compact scheduling of zero-one time operations in multi-stage systems ⋮ Complexity of approximation of 3-edge-coloring of graphs ⋮ On multiples of simple graphs and Vizing's theorem ⋮ Approximating the max-edge-coloring problem ⋮ Decompositions for edge-coloring join graphs and cobipartite graphs ⋮ Two easy duality theorems for product partial orders ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Edge-coloring of 3-uniform hypergraphs ⋮ The complexity of list edge-partitions for simple graphs ⋮ Approximation algorithm for maximum edge coloring ⋮ Local edge colouring of Yao-like subgraphs of unit disk graphs ⋮ The chromatic index of a graph whose core is a cycle of order at most 13 ⋮ Characterization of a class of graphs related to pairs of disjoint matchings ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small ⋮ Achieving maximum chromatic index in multigraphs ⋮ On star and caterpillar arboricity ⋮ On linear k-arboricity ⋮ Some results on graphs without long induced paths ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ 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 ⋮ The chromatic index of graphs with large maximum degree ⋮ Embedding partial Steiner triple systems is NP-complete ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Decomposition by clique separators ⋮ Some sufficient conditions for a graph to be of \(C_f\) 1 ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs ⋮ \((p,k)\)-coloring problems in line graphs
This page was built for publication: The NP-Completeness of Edge-Coloring
