A fast algorithm for equitable coloring
From MaRDI portal
Publication:532129
DOI10.1007/s00493-010-2483-5zbMath1224.05176OpenAlexW2084709397WikidataQ60060509 ScholiaQ60060509MaRDI QIDQ532129
Endre Szemerédi, Marcelo Mydlarz, Alexandr V. Kostochka, Henry A. Kierstead
Publication date: 26 April 2011
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-010-2483-5
Related Items
Improving lower bounds for equitable chromatic number ⋮ Every 4-Colorable Graph With Maximum Degree 4 Has an Equitable 4-Coloring ⋮ On the Corrádi-Hajnal theorem and a question of Dirac ⋮ A Tabu Search Heuristic for the Equitable Coloring Problem ⋮ Equitable clique-coloring in claw-free graphs with maximum degree at most 4 ⋮ On equitable colouring of Knödel graphs ⋮ Asymptotic multipartite version of the Alon-Yuster theorem ⋮ Equitable colorings of corona multiproducts of graphs ⋮ A greedy algorithm for the social golfer and the Oberwolfach problem ⋮ Computing the partition function for graph homomorphisms with multiplicities ⋮ Results about the total chromatic number and the conformability of some families of circulant graphs ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Approximate multipartite version of the Hajnal-Szemerédi theorem ⋮ A note on relaxed equitable coloring of graphs ⋮ Extremal numbers for disjoint copies of a clique ⋮ Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs ⋮ An Extension of the Hajnal–Szemerédi Theorem to Directed Graphs ⋮ Equitable two-colorings of uniform hypergraphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A flow based pruning scheme for enumerative equitable coloring algorithms ⋮ Edge-decompositions of graphs with high minimum degree ⋮ A refinement of a result of Corrádi and Hajnal ⋮ Constructing Armstrong tables for general cardinality constraints and not-null constraints ⋮ Equitable partition of planar graphs ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ On equitable colorings of hypergraphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms ⋮ Equitable colorings of hypergraphs with few edges ⋮ Introduction to dominated edge chromatic number of a graph ⋮ Equitable total-coloring of subcubic graphs ⋮ Equitable List Coloring of Graphs with Bounded Degree ⋮ Equitable partition of graphs into induced forests ⋮ Equitable colourings of Borel graphs ⋮ A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs
Cites Work
- Unnamed Item
- Ore-type versions of Brooks' theorem
- Spanning subgraphs of random graphs
- Blow-up lemma
- Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
- An Ore-type theorem on equitable coloring
- Ore-type graph packing problems
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- The infamous upper tail
- Perfect Graphs and an Application to Optimizing Municipal Services
This page was built for publication: A fast algorithm for equitable coloring
