GCol: A Library for Graph Coloring

GCol is an open-source Python library for graph coloring that is built on top of the NetworkX package. It provides easy-to-use, high-performance algorithms for node coloring, edge coloring, face coloring, equitable coloring, weighted coloring, precoloring, and maximum independent set identification. It also offers several tools for solution visualization.

In general, graph coloring problems are NP-hard. This library therefore offers both exponential-time exact algorithms and polynomial-time heuristic algorithms.

Contents:

• 1. General Info
  • 1.1. Quick Start
  • 1.2. Textbook
  • 1.3. Support
  • 1.4. MIT License
• 2. An Introduction to the GCol Library
  • 2.1. Getting Started
  • 2.2. Node Coloring and Visualization
  • 2.3. Color Palettes
  • 2.4. Edge Coloring and Visualization
  • 2.5. Face Coloring and Visualization
  • 2.6. Precoloring
  • 2.7. Solving Sudoku
  • 2.8. \(k\)-Coloring
    • 2.8.1. Equitable \(k\)-coloring
    • 2.8.2. Minimum Cost \(k\)-Coloring
  • 2.9. Kempe Chains
  • 2.10. Independent Sets, Cliques and Coverings
• 3. Case Study: Exam Timetabling
  • 3.1. Background
  • 3.2. An Initial Solution
  • 3.3. Scheduling Large Exams First
  • 3.4. Balancing Exams
  • 3.5. Limiting Timeslots
• 4. Performance Analysis
  • 4.1. Differing Node Coloring Strategies
  • 4.2. Comparison to NetworkX
  • 4.3. Exact Algorithm Performance
  • 4.4. Equitable Coloring
  • 4.5. Independent Set Comparison
• 5. Gallery
  • 5.1. Complete Graphs
  • 5.2. Cycle Graphs
  • 5.3. Wheel Graphs
  • 5.4. Trees
  • 5.5. Planar Graphs
  • 5.6. Triangulations of Images
  • 5.7. Coloring Street Maps
• 6. Documentation
  • chromatic_index()
  • chromatic_number()
  • coloring_layout()
  • draw_face_coloring()
  • edge_coloring()
  • edge_k_coloring()
  • edge_precoloring()
  • equitable_edge_k_coloring()
  • equitable_face_k_coloring()
  • equitable_node_k_coloring()
  • face_chromatic_number()
  • face_coloring()
  • face_k_coloring()
  • face_precoloring()
  • get_edge_colors()
  • get_node_colors()
  • get_set_colors()
  • kempe_chain()
  • max_independent_set()
  • min_cost_k_coloring()
  • multipartite_layout()
  • node_coloring()
  • node_k_coloring()
  • node_precoloring()
  • partition()

• Index

• Module Index

• Search Page