On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic

DOI10.1016/j.disopt.2011.04.004zbMath1242.05085OpenAlexW2164841845MaRDI QIDQ666002

Alain Hertz, Gilles Caporossi, Sivan Altinakar

Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2011.04.004

zbMATH Keywords

consecutive edge-coloringscyclic edge-coloringsinterval edge-colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item

Cites Work

• Lower bounds and a tabu search algorithm for the minimum deficiency problem
• On interval edge colorings of \((\alpha ,\beta )\)-biregular bipartite graphs
• On the deficiency of bipartite graphs
• Chromatic scheduling in a cyclic open shop
• Compact cyclic edge-colorings of graphs
• The deficiency of a regular graph
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Interval colorings of edges of a multigraph
• Compact Scheduling In Open Shop With Zero-One Time Operations
• Consecutive colorings of the edges of general graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item