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, list coloring, 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. Publications
  • 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. Edge Coloring and Visualization
  • 2.4. Face Coloring and Visualization
  • 2.5. Precoloring
  • 2.6. Solving Sudoku
  • 2.7. List Coloring
  • 2.8. \(k\)-Coloring
    • 2.8.1. Equitable \(k\)-coloring
    • 2.8.2. Minimum Cost \(k\)-Coloring
  • 2.9. Kempe Chains and \(s\)-Chains
  • 2.10. Independent Sets, Cliques and Coverings
• 3. Node Placement and Color Palettes
  • 3.1. Node Placement
  • 3.2. Color Palettes
• 4. Case Study: Exam Timetabling
  • 4.1. Background
  • 4.2. An Initial Solution
  • 4.3. Scheduling Large Exams First
  • 4.4. Balancing Exams
  • 4.5. Limiting Timeslots
• 5. Performance Analysis
  • 5.1. Differing Node Coloring Strategies
  • 5.2. Optimization Output
  • 5.3. Comparison to NetworkX
  • 5.4. Exact Algorithm Performance
  • 5.5. Local Search Comparison
  • 5.6. Equitable Coloring
  • 5.7. Independent Set Comparison
• 6. Gallery
  • 6.1. Complete Graphs
  • 6.2. Cycle Graphs
  • 6.3. Wheel Graphs
  • 6.4. Trees
  • 6.5. Planar Graphs
  • 6.6. Interval Graphs
  • 6.7. Triangulations of Images
  • 6.8. Coloring Street Maps
  • 6.9. Mondrian Art
  • 6.10. An April Fool’s Joke
• 7. Documentation
  • 7.1. Edge Coloring
    • chromatic_index()
    • edge_coloring()
    • edge_k_coloring()
    • edge_list_coloring()
    • edge_precoloring()
    • equitable_edge_k_coloring()
  • 7.2. Face Coloring
    • dual_graph()
    • equitable_face_k_coloring()
    • face_chromatic_number()
    • face_coloring()
    • face_k_coloring()
    • face_list_coloring()
    • face_precoloring()
  • 7.3. Node Coloring
    • chromatic_number()
    • equitable_node_k_coloring()
    • kempe_chain()
    • max_independent_set()
    • min_cost_k_coloring()
    • node_coloring()
    • node_k_coloring()
    • node_list_coloring()
    • node_precoloring()
    • s_chain()
  • 7.4. Output
    • coloring_layout()
    • draw_face_coloring()
    • get_edge_colors()
    • get_node_colors()
    • get_set_colors()
    • multipartite_layout()
    • partition()

• Index

• Module Index

• Search Page