Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms

DOI10.1515/acsc-2016-0016zbMath1457.05035OpenAlexW2524076789MaRDI QIDQ4971668

Hanna Furmańczyk, Andrzej Jastrzȩbski, Marek Kubale

Publication date: 12 October 2020

Published in: Archives of Control Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/acsc-2016-0016

zbMATH Keywords

NP-hardnesscomputer experimentsequitable chromatic numbercorona graphpolynomial heuristicsequitable coloring conjectures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Improving lower bounds for equitable chromatic number ⋮ On equitable chromatic number of Tadpole graph T_{m,n} ⋮ Equitable oriented coloring ⋮ New results on the robust coloring problem ⋮ Bounded colouring motivated by the limited resource partially concurrent open shop problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equitable \(\Delta\)-coloring of graphs
• A fast algorithm for equitable coloring
• Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture
• Equitable colorings of Kronecker products of graphs
• Equitable colorings of planar graphs with maximum degree at least nine
• Equitable colorings of Cartesian products of graphs
• Equitable colorings of bounded treewidth graphs
• Equitable coloring of trees
• Equitable coloring and the maximum degree
• Interval vertex-coloring of a graph with forbidden colors
• On equitable coloring of bipartite graphs
• \(H\)-factors in dense graphs
• Equitable colorings of planar graphs without short cycles
• Equivalence of two conjectures on equitable coloring of graphs
• An Ore-type theorem on equitable coloring
• Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• On colouring random graphs
• Equitable Coloring
• The infamous upper tail
• Equitable coloring of Kneser graphs
• On the equitable chromatic number of complete \(n\)-partite graphs

This page was built for publication: Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms