A fast algorithm for equitable coloring
An equitable \(k\)-colouring of a graph is a proper vertex colouring with \(k\) colors, in which the sizes of any two colour classes differ by at most one. It was conjectured by P. Erdős and proved by \textit{A. Hajnal} and \textit{E. Szemerédi} [Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 601--623 (1970; Zbl 0217.02601)] that every graph with maximum degree at most \(r\) admits an equitable \((r+1)\)-colouring. The authors present a less complicated and shorter proof of this celebrated Hajnal-Szemerédi theorem by using new methods and recombining old ideas. Their proof yields, moreover, a simple \(O(rn^2)\) time algorithm for obtaining an equitable \((r+1)\)-colouring, where \(n\) is the vertex number of the given graph with maximum degree at most \(r\). This algorithm is faster than those obtained previously in [\textit{H. A. Kierstead} and \textit{A. V. Kostochka}, Comb. Probab. Comput. 17, No.~2, 265--270 (2008; Zbl 1163.05015); \textit{M. Mydlarz and E. Szemerédi}, Algorithmic Brooks' theorem, manuscript]. \textit{H. A. Kierstead} and \textit{A. V. Kostochka} [J. Comb. Theory, Ser. B 98, No.~1, 226--234 (2008; Zbl 1127.05039)] improved the Hajnal-Szemerédi theorem by showing that any graph, in which the degree sum of any two adjacent vertices is at most \(2r+1\), has an equitable \((r+1)\)-colouring. The authors conjecture that such a colouring can be constructed by a polynomial time algorithm.
- An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
- A fast algorithm for computing a nearly equitable edge coloring with balanced conditions
- A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
- A polyhedral approach for the equitable coloring problem
- A DSATUR-based algorithm for the equitable coloring problem
- Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
- scientific article; zbMATH DE number 1302199
- scientific article; zbMATH DE number 7058467
- Structural parameterizations for equitable coloring
- scientific article; zbMATH DE number 3378938
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- An Ore-type theorem on equitable coloring
- Blow-up lemma
- scientific article; zbMATH DE number 949303 (Why is no real title available?)
- Ore-type graph packing problems
- Ore-type versions of Brooks' theorem
- Perfect Graphs and an Application to Optimizing Municipal Services
- Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
- Spanning subgraphs of random graphs
- The infamous upper tail
- Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
- A flow based pruning scheme for enumerative equitable coloring algorithms
- A note on relaxed equitable coloring of graphs
- Equitable partition of planar graphs
- Improving lower bounds for equitable chromatic number
- Constructing Armstrong tables for general cardinality constraints and not-null constraints
- The complexity of perfect matchings and packings in dense hypergraphs
- On equitable colorings of hypergraphs
- Equitable colorings of hypergraphs with few edges
- Equitable total-coloring of subcubic graphs
- Equitable partition of graphs into induced forests
- A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs
- Asymptotic multipartite version of the Alon-Yuster theorem
- Equitable colorings of corona multiproducts of graphs
- A polyhedral approach for the equitable coloring problem
- An Ore-type theorem on equitable coloring
- Equitable clique-coloring in claw-free graphs with maximum degree at most 4
- A greedy algorithm for the social golfer and the Oberwolfach problem
- Equitable list coloring of graphs with bounded degree
- Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring
- On equitable colouring of Knödel graphs
- A fast algorithm for computing a nearly equitable edge coloring with balanced conditions
- A tabu search heuristic for the equitable coloring problem
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- A DSATUR-based algorithm for the equitable coloring problem
- On the Corrádi-Hajnal theorem and a question of Dirac
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- Approximate multipartite version of the Hajnal-Szemerédi theorem
- scientific article; zbMATH DE number 2079370 (Why is no real title available?)
- Equitable two-colorings of uniform hypergraphs
- Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
- Introduction to dominated edge chromatic number of a graph
- Equitable colourings of Borel graphs
- A refinement of a result of Corrádi and Hajnal
- An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
- A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
- An extension of the Hajnal-Szemerédi theorem to directed graphs
- scientific article; zbMATH DE number 7058467 (Why is no real title available?)
- New Bounds for the Nearly Equitable Edge Coloring Problem
- Edge-decompositions of graphs with high minimum degree
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- 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
- Extremal numbers for disjoint copies of a clique
- Equitable colorings of \(l\)-corona products of cubic graphs
- Equitable coloring of graphs beyond planarity
- A polynomial-time algorithm for conformable coloring on regular bipartite and subcubic graphs
- Equitable coloring of planar graphs without 5-cycles and chordal 4-cycles
- Equitable list coloring of planar graphs with given maximum degree
- Clique factors in pseudorandom graphs
- The equitable chromatic number of circulant graphs with maximum degree at most 4
- Competitive capacitated online recoloring
- Targeted least cardinality candidate key for relational databases
- Computing the partition function for graph homomorphisms with multiplicities
This page was built for publication: A fast algorithm for equitable coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q532129)
