Exploring k-Colorability

2007/02/09 by Kia Kai Li, Li, Kia Kai
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.CC

paper · pdf · doi:10.48550/arxiv.cs/0702058

arxiv created 2007/02/09 · openalex publication_date 2007/02/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An introductory paper to the graph k-colorability problem.

Related

• k-Colorability of P5-free graphs
• Coloring k-colorable graphs using relatively small palettes
• Improved Hardness of Approximating Chromatic Number
• Graph colouring algorithms
• Deciding k-colourability of P₅-free graphs in polynomial time