NP completeness of finding the chromatic index of regular graphs

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(only showing first 100 items - show all)

Approximating the maximum 3-edge-colorable subgraph problem
The strong chromatic number of partial triple systems
Edge-packings of graphs and network reliability
NP-completeness of edge-colouring some restricted graphs
Near-optimal, distributed edge colouring via the nibble method
Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
Total colouring regular bipartite graphs is NP-hard
The hardness of approximation: Gap location
The probabilistic method yields deterministic parallel algorithms
Covering regular graphs
Short solution of Kotzig's problem for bipartite graphs
Trees, paths, stars, caterpillars and spiders
Minimum multiplicity edge coloring via orientation
Is there any polynomial upper bound for the universal labeling of graphs?
Classifying $k$-edge colouring for $H$-free graphs
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
On sum coloring of graphs
The multi-league sports scheduling problem, or how to schedule thousands of matches
The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
Parameterized complexity of \textsc{maximum edge colorable subgraph}
Complexity and algorithms for injective edge-coloring in graphs
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
Colouring simplicial complexes via the Lechuga-Murillo's model
Star colouring of bounded degree graphs and regular graphs
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
Regular pattern-free coloring
Colouring $(P_r + P_s)$-free graphs
Complexity-separating graph classes for vertex, edge and total colouring
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
A note on connected greedy edge colouring
The complexity of counting edge colorings for simple graphs
List coloring in the absence of a linear forest
Chromatic index of graphs with no cycle with a unique chord
On strong proper connection number of cubic graphs
$H$-colouring $P_t$-free graphs in subexponential time
Colouring square-free graphs without long induced paths
Complexity separating classes for edge-colouring and total-colouring
Narrow sieves for parameterized paths and packings
Colorful edge decomposition of graphs: some polynomial cases
Coloring graphs without short cycles and long induced paths
The complexity of the proper orientation number
The hunting of a snark with total chromatic number 5
Packing $[1, \Delta ]$-factors in graphs of small degree
The satisfactory partition problem
On the algorithmic complexity of zero-sum edge-coloring
Injective coloring of graphs revisited
3-colouring $P_t$-free graphs without short odd cycles
A Markov chain on the solution space of edge colorings of bipartite graphs
4-coloring $H$-free graphs when $H$ is small
4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
A survey on the computational complexity of coloring graphs with forbidden subgraphs
On the equitable total chromatic number of cubic graphs
Pairwise-interaction games
List coloring in the absence of a linear forest
The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
Colouring square-free graphs without long induced paths
The parameterised complexity of list problems on graphs of bounded treewidth
Complexity of coloring graphs without paths and cycles
Edge-colouring and total-colouring chordless graphs
On the parameterized complexity of coloring graphs in the absence of a linear forest
Multi-switch: a tool for finding potential edge-disjoint 1-factors
On the complexity of deciding whether the regular number is at most two
Improved complexity results on $k$-coloring $P_t$-free graphs
Colouring (P_r+P_s)-Free Graphs
Colouring H-free graphs of bounded diameter.
scientific article; zbMATH DE number 7426494 (Why is no real title available?)
Obstructions for three-coloring and list three-coloring H-free graphs
Injective edge coloring of graphs
scientific article; zbMATH DE number 7651161 (Why is no real title available?)
ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR
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
On 3-coloring of $(2P_4,C_5)$-free graphs
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
Vertex-critical ( P₃ + P₁ )-free and vertex-critical (gem, co-gem)-free graphs
Total chromatic number of unichord-free graphs
List-3-coloring ordered graphs with a forbidden induced subgraphs
The hardness of recognising poorly matchable graphs and the hunting of the $d$-snark
On balanceable and simply balanceable regular graphs
Vertex-critical (P₅,W₄)-free graphs
Hardness transitions of star colouring and restricted star colouring
Computational complexity of covering multigraphs with semi-edges: small cases
Recognition and proper coloring of unit segment intersection graphs
Harmonious colourings of temporal matchings
Acyclic, star and injective colouring: a complexity picture for H-free graphs
Some results on critical (P₅, H)-free graphs
A polynomial-time algorithm for conformable coloring on regular bipartite and subcubic graphs
Some results on critical (P₅,H)-free graphs
Vertex-critical graphs in co-gem-free graphs

This page was built for publication: NP completeness of finding the chromatic index of regular graphs

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