The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3

DOI10.1016/S0096-3003(96)00021-5zbMath0876.05030OpenAlexW2044028427MaRDI QIDQ1354146

Diamantis P. Koreas

Publication date: 12 November 1997

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0096-3003(96)00021-5

zbMATH Keywords

graphedge-coloringNP-completenesschromatic index

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS ⋮ Subcubic planar graphs of girth 7 are class I ⋮ Edge-colouring graphs with bounded local degree sums ⋮ The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks ⋮ On Vizing's edge colouring question ⋮ ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS ⋮ 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 ⋮ Total tessellation cover: bounds, hardness, and applications ⋮ Injective edge coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The NP-Completeness of Edge-Coloring
• Using euler partitions to edge color bipartite multigraphs

This page was built for publication: The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3