A note on the Cornaz-Jost transformation to solve the graph coloring problem
From MaRDI portal
Publication:2444903
DOI10.1016/j.ipl.2013.05.014zbMath1284.68289MaRDI QIDQ2444903
Monia Giandomenico, Fabrizio Rossi, Flavia Bonomo-Braberman
Publication date: 11 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2013.05.014
computational complexity; polynomial-time algorithm; graph coloring problem; graph operators; max-coloring problem
Related Items
Solving vertex coloring problems as maximum weight stable set problems, A note on selective line-graphs and partition colorings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong perfect graph theorem
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- The ellipsoid method and its consequences in combinatorial optimization
- Batch processing with interval graph compatibilities between tasks
- A one-to-one correspondence between colorings and stable sets
- Independent Sets of Maximum Weight in Apple-Free Graphs