Improved Edge-Coloring with Three Colors

DOI10.1007/11917496_9zbMATH Open1167.05315OpenAlexW2152302158MaRDI QIDQ3522945FDOQ3522945

Authors: Łukasz Kowalik 

Publication date: 4 September 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11917496_9

Recommendations

• Improved edge-coloring with three colors
• A better than “best possible” algorithm to edge color multigraphs
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Colorings with few colors: counting, enumeration and combinatorial bounds

Mathematics Subject Classification ID

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

Cited In (6)

• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
• Improved edge-coloring with three colors
• Approximating the maximum 3-edge-colorable subgraph problem
• Tight lower bounds for list edge coloring
• On the partition of 3-colorable graphs
• 3-coloring in time

This page was built for publication: Improved Edge-Coloring with Three Colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522945)