Equitable coloring extends Chernoff-Hoeffding bounds

DOI10.1007/3-540-44666-4_31MaRDI QIDQ4780802zbMATH OpenFDO

Authors Sriram Pemmaraju

Publication date 21 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2129/21290285

Mathematics Subject Classification ID

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

Recommendations

• Equitable colorings extend Chernoff-Hoeffding bounds
• scientific article; zbMATH DE number 6452992
• scientific article; zbMATH DE number 437558
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• \(t\)-wise independence with local dependencies

Cited in

(36)

• Ore-type versions of Brooks' theorem
• Total equitable list coloring
• Equitable coloring of some convex polytope graphs
• A note on the equitable choosability of complete bipartite graphs
• On list equitable total colorings of the generalized theta graph
• Proportional 2-choosability with a bounded palette
• On the equitable choosability of the disjoint union of stars
• Improving lower bounds for equitable chromatic number
• A simple characterization of proportionally 2-choosable graphs
• Derandomizing local distributed algorithms under bandwidth restrictions
• Proportional choosability: a new list analogue of equitable coloring
• A polyhedral approach for the equitable coloring problem
• An Ore-type theorem on equitable coloring
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• Proportional choosability of complete bipartite graphs
• Equitable colorings extend Chernoff-Hoeffding bounds
• Equitable coloring of random graphs
• scientific article; zbMATH DE number 437558 (Why is no real title available?)
• A tabu search heuristic for the equitable coloring problem
• A DSATUR-based algorithm for the equitable coloring problem
• The Randomized Coloring Procedure with Symmetry-Breaking
• Equitable and list equitable colorings of planar graphs without 4-cycles
• Linear classifiers are nearly optimal when hidden variables have diverse effects
• Distributed arboricity-dependent graph coloring via all-to-all communication
• A refinement of a result of Corrádi and Hajnal
• scientific article; zbMATH DE number 6452992 (Why is no real title available?)
• Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture
• Equitable colorings of Kronecker products of graphs
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Improved distributed approximations for maximum independent set
• Equitable list coloring of sparse graphs
• Constant-round spanners and shortest paths in congested clique and MPC
• Equitable defective coloring of sparse planar graphs
• Equitable colorings of Cartesian products of graphs
• On equitable -coloring of graphs with low average degree
• \(t\)-wise independence with local dependencies

This page was built for publication: Equitable coloring extends Chernoff-Hoeffding bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4780802)