Improved edge-coloring with three colors

DOI10.1016/j.tcs.2009.05.005zbMath1171.68031OpenAlexW2068633285WikidataQ56390683 ScholiaQ56390683MaRDI QIDQ837164

Łukasz Kowalik

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.005

zbMATH Keywords

algorithmedge-coloringmeasure and conquerexponential-time

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Switching 3-edge-colorings of cubic graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ Interpretable random forest model for identification of edge 3-uncolorable cubic graphs ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Pathwidth of cubic graphs and exact algorithms
• A note on the complexity of the chromatic number problem
• Computer science today. Recent trends and developments
• Measure and conquer
• A fast parallel algorithm for routing in permutation networks
• The NP-Completeness of Edge-Coloring
• A survey on snarks and new results: Products, reducibility and a computer search
• Applications of matching and edge‐coloring algorithms to routing in clos networks
• 3-coloring in time
• Automata, Languages and Programming
• Algorithms and Data Structures

This page was built for publication: Improved edge-coloring with three colors