The smallest hard-to-color graph

DOI10.1016/0012-365X(91)90313-QzbMath0759.05038OpenAlexW2091345593MaRDI QIDQ1185079

Julio Kuplinsky, Pierre Hansen

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0012-365x(91)90313-q

zbMATH Keywords

chromatic numberhard-to-color graphsequential largest-first algorithmvertex coloring algorithm

Mathematics Subject Classification ID

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

Related Items (3)

Hard-to-color graphs for connected sequential colorings ⋮ The smallest hard-to-color graph for the SL algorithm ⋮ Online algorithms for the maximum \(k\)-colorable subgraph problem

Cites Work

• Sequential coloring versus Welsh-Powell bound
• Improving the performance guarantee for approximate graph coloring
• Four classes of perfectly orderable graphs
• The Complexity of Near-Optimal Graph Coloring
• On Various Algorithms for Estimating the Chromatic Number of a Graph
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The smallest hard-to-color graph