NP-completeness of edge-colouring some restricted graphs

DOI10.1016/0166-218X(91)90010-TzbMath0797.68078OpenAlexW2068894266MaRDI QIDQ1173977

John A. Ellis, Leizhen Cai

Publication date: 25 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90010-t

zbMATH Keywords

NP-completenessperfect graphsclaw-free graphscomparability graphschromatic index of regular graphregular line graphs

Mathematics Subject Classification ID

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

Related Items (26)

Edge-colouring of join graphs ⋮ Trees, paths, stars, caterpillars and spiders ⋮ Characterizing and edge-colouring split-indifference graphs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Edge-colouring graphs with bounded local degree sums ⋮ On edge-colouring indifference graphs ⋮ Edge Coloring of Split Graphs ⋮ Decompositions for the edge colouring of reduced indifference graphs. ⋮ Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs ⋮ Total chromatic number of unichord-free graphs ⋮ Graph edge coloring: a survey ⋮ Edge colouring line graphs of unicyclic graphs ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ On the chromatic index of join graphs and triangle-free graphs with large maximum degree ⋮ The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ Decompositions for edge-coloring join graphs and cobipartite graphs ⋮ Detecting strong cliques ⋮ On edge-colouring indifference graphs ⋮ Unnamed Item ⋮ Revising Johnson's table for the 21st century ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ On cocolourings and cochromatic numbers of graphs ⋮ The \(b\)-chromatic index of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sur l'indice chromatique du graphe représentatif des arêtes d'un graphe régulier
• From the theory of regular graphs of third and fourth degree
• The NP-completeness column: an ongoing guide
• The NP-Completeness of Edge-Coloring
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• NP completeness of finding the chromatic index of regular graphs
• Regular Graphs with Given Girth and Restricted Circuits

This page was built for publication: NP-completeness of edge-colouring some restricted graphs