A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring

DOI10.1017/S0963548307008619zbMath1163.05015WikidataQ60060517 ScholiaQ60060517MaRDI QIDQ3512604

Alexandr V. Kostochka, Henry A. Kierstead

Publication date: 21 July 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (52)

The strong equitable vertex 2-arboricity of complete bipartite and tripartite graphs ⋮ Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs ⋮ An Ore-type theorem on Hamiltonian square cycles ⋮ Equitable clique-coloring in claw-free graphs with maximum degree at most 4 ⋮ Equitable colorings of Kronecker products of graphs ⋮ Asymptotic multipartite version of the Alon-Yuster theorem ⋮ Equitable vertex arboricity of 5-degenerate graphs ⋮ Equitable colorings of planar graphs without short cycles ⋮ Equitable vertex arboricity of graphs ⋮ A large tree is \(tK_m\)-good ⋮ Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu ⋮ Rainbow spanning structures in graph and hypergraph systems ⋮ Equitable critical graphs ⋮ A STUDY ON EQUITABLE CHROMATIC AND THRESHOLD OF MYCIELSKIAN OF GRAPHS ⋮ Approximate multipartite version of the Hajnal-Szemerédi theorem ⋮ Extremal problems in hypergraph colourings ⋮ A note on relaxed equitable coloring of graphs ⋮ On multipartite Hajnal-Szemerédi theorems ⋮ An Extension of the Hajnal–Szemerédi Theorem to Directed Graphs ⋮ Equitable two-colorings of uniform hypergraphs ⋮ A polyhedral approach for the equitable coloring problem ⋮ On the KŁR conjecture in random graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Monochromatic bounded degree subgraph partitions ⋮ A refinement of a result of Corrádi and Hajnal ⋮ \(K_r\)-factors in graphs with low independence number ⋮ A fast algorithm for equitable coloring ⋮ Constructing Armstrong tables for general cardinality constraints and not-null constraints ⋮ Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture ⋮ Equitable partition of planar graphs ⋮ A note on regular Ramsey graphs ⋮ Equitable neighbour-sum-distinguishing edge and total colourings ⋮ On equitable colorings of sparse graphs ⋮ Sets of unit vectors with small subset sums ⋮ Ore-type versions of Brooks' theorem ⋮ On equitable colorings of hypergraphs ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs ⋮ Stackelberg network pricing is hard to approximate ⋮ Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms ⋮ Equitable colorings of hypergraphs with few edges ⋮ An improved upper bound on the density of universal random graphs ⋮ Continuity of Multimarginal Optimal Transport with Repulsive Cost ⋮ Equitable colorings of planar graphs with maximum degree at least nine ⋮ Equitable colorings of Cartesian products of graphs ⋮ Coloring by two-way independent sets ⋮ TILING DIRECTED GRAPHS WITH TOURNAMENTS ⋮ Equitable List Coloring of Graphs with Bounded Degree ⋮ Equitable colourings of Borel graphs ⋮ Equitable list-coloring for \(C_{5}\)-free plane graphs without adjacent triangles ⋮ A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs ⋮ A degree sequence Hajnal-Szemerédi theorem

Cites Work

• Unnamed Item
• Proof of the Seymour conjecture for large graphs
• Equitable coloring and the maximum degree
• Hamiltonian square-paths
• Note on Hamilton Circuits
• Ore-type graph packing problems
• A list analogue of equitable coloring
• The infamous upper tail
• Perfect Graphs and an Application to Optimizing Municipal Services

This page was built for publication: A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring