Tight Lower Bounds for List Edge Coloring

DOI10.4230/LIPIcs.SWAT.2018.28zbMath1477.68235arXiv1804.02537OpenAlexW2964101152MaRDI QIDQ5116492

Arkadiusz Socała, Łukasz Kowalik

Publication date: 25 August 2020

Full work available at URL: https://arxiv.org/abs/1804.02537

zbMATH Keywords

complexitylist edge coloringETH lower bound

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Optimal channel assignment with list-edge coloring ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors

Cites Work

• Unnamed Item
• A simplified NP-complete satisfiability problem
• List edge and list total colourings of multigraphs
• Which problems have strongly exponential complexity?
• The list chromatic index of a bipartite multigraph
• Narrow sieves for parameterized paths and packings
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Set Partitioning via Inclusion-Exclusion
• The NP-Completeness of Some Edge-Partition Problems
• Tight Lower Bounds on Graph Embedding Problems
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Tight Lower Bounds for List Edge Coloring