NP completeness of finding the chromatic index of regular graphs
From MaRDI portal
Publication:4747513
DOI10.1016/0196-6774(83)90032-9zbMath0509.68037OpenAlexW1966769222MaRDI QIDQ4747513
Publication date: 1983
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(83)90032-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Colouring simplicial complexes via the Lechuga-Murillo's model, ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR, Star colouring of bounded degree graphs and regular graphs, The hardness of approximation: Gap location, 4-Coloring H-Free Graphs When H Is Small, Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four, On the equitable total chromatic number of cubic graphs, The probabilistic method yields deterministic parallel algorithms, On the algorithmic complexity of zero-sum edge-coloring, Trees, paths, stars, caterpillars and spiders, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, The strong chromatic number of partial triple systems, Complexity separating classes for edge-colouring and total-colouring, The parameterised complexity of list problems on graphs of bounded treewidth, Complexity of coloring graphs without paths and cycles, Edge-packings of graphs and network reliability, Narrow sieves for parameterized paths and packings, Going wide with the 1-2-3 conjecture, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, On total and edge coloring some Kneser graphs, Colorful edge decomposition of graphs: some polynomial cases, Regular pattern-free coloring, Minimum multiplicity edge coloring via orientation, Colouring square-free graphs without long induced paths., Covering regular graphs, Colouring \((P_r + P_s)\)-free graphs, Is there any polynomial upper bound for the universal labeling of graphs?, Edge-colouring and total-colouring chordless graphs, Complexity-separating graph classes for vertex, edge and total colouring, A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs, Acyclic chromatic index of chordless graphs, Near-optimal distributed edge coloring, Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs, Hardness transitions and uniqueness of acyclic colouring, Unnamed Item, Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs, Injective coloring of graphs revisited, Determining the total colouring number is NP-hard, 3-colouring \(P_t\)-free graphs without short odd cycles, A Markov chain on the solution space of edge colorings of bipartite graphs, Total chromatic number of unichord-free graphs, Coloring graphs without short cycles and long induced paths, 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, On the parameterized complexity of coloring graphs in the absence of a linear forest, The complexity of the proper orientation number, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, The hunting of a snark with total chromatic number 5, NP-completeness of edge-colouring some restricted graphs, A note on connected greedy edge colouring, Packing \([1, \Delta \)-factors in graphs of small degree], The complexity of counting edge colorings for simple graphs, Classifying \(k\)-edge colouring for \(H\)-free graphs, On the complexity of deciding whether the regular number is at most two, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, The multi-league sports scheduling problem, or how to schedule thousands of matches, Pairwise-Interaction Games, Approximating the maximum 2- and 3-edge-colorable subgraph problems, List coloring in the absence of a linear forest, The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness, Chromatic index of graphs with no cycle with a unique chord, The satisfactory partition problem, Parameterized complexity of \textsc{maximum edge colorable subgraph}, Approximately coloring graphs without long induced paths, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Complexity and algorithms for injective edge-coloring in graphs, Multi-switch: A tool for finding potential edge-disjoint 1-factors, NP-completeness results for partitioning a graph into total dominating sets, Complexity of fall coloring for restricted graph classes, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, On 3-coloring of \((2P_4,C_5)\)-free graphs, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, On 3-coloring of \((2P_4,C_5)\)-free graphs, On sum coloring of graphs, Colouring (P_r+P_s)-Free Graphs, Near-optimal, distributed edge colouring via the nibble method, Colouring H-free graphs of bounded diameter., On strong proper connection number of cubic graphs, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, Short solution of Kotzig's problem for bipartite graphs, List Coloring in the Absence of a Linear Forest, \(H\)-colouring \(P_t\)-free graphs in subexponential time, Colouring square-free graphs without long induced paths, Approximating the maximum 3-edge-colorable subgraph problem, Parameterized complexity of maximum edge colorable subgraph, Vizing's and Shannon's theorems for defective edge colouring, On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs, Unnamed Item, Injective edge coloring of graphs, Total colouring regular bipartite graphs is NP-hard
