On the complexity of determining the irregular chromatic index of a graph

DOI10.1016/j.jda.2014.12.008zbMath1320.05036OpenAlexW2083522205MaRDI QIDQ2253909

Olivier Baudon, Julien Bensmail, Eric Sopena

Publication date: 13 February 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.12.008

zbMATH Keywords

edge colouringlocally irregular graphirregular graphirregular chromatic index

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items

A Note on the Locally Irregular Edge Colorings of Cacti, A note on the weak \((2,2)\)-conjecture, New bounds for locally irregular chromatic index of bipartite and subcubic graphs, Decomposing graphs into a constant number of locally irregular subgraphs, On locally irregular decompositions of subcubic graphs, Decomposing degenerate graphs into locally irregular subgraphs, Colorful edge decomposition of graphs: some polynomial cases, Locally irregular edge-coloring of subcubic graphs, Local irregularity conjecture for 2-multigraphs versus cacti, On decomposing multigraphs into locally irregular submultigraphs, Local irregularity conjecture vs. cacti, Algorithmic complexity of weakly semiregular partitioning and the representation number, Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture, Decomposing split graphs into locally irregular graphs, Decomposing split graphs into locally irregular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic complexity of proper labeling problems
• A dynamic survey of graph labeling
• Edge weights and vertex colours
• On decomposing regular graphs into locally irregular subgraphs
• Vertex colouring edge partitions
• Highly irregular graphs
• A Tight Bound on the Irregularity Strength of Graphs