A fast algorithm for equitable coloring

Henry A. Kiersteád, Alexandr Kostochka, Marcelo Mydlarz, Endre Szemerédi

Type: Article

Publication Date: 2010-03-01

Citations: 86

DOI: https://doi.org/10.1007/s00493-010-2483-5

View Publication

Download PDF

Locations

CiteSeer X (The Pennsylvania State University) - View - PDF
COMBINATORICA - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	An exact DSatur-based algorithm for the Equitable Coloring Problem	2013	Isabel Méndez‐Díaz Graciela Nasini Daniel Severín
+ PDF Chat	A DSATUR-based algorithm for the Equitable Coloring Problem	2014	Isabel Méndez‐Díaz Graciela Nasini Daniel Severín
+ PDF Chat	A flow based pruning scheme for enumerative equitable coloring algorithms	2017	Arie M. C. A. Koster Robert Scheidweiler Martin Tieves
+ PDF Chat	A Tabu Search Heuristic for the Equitable Coloring Problem	2014	Isabel Méndez Díaz Graciela Nasini Daniel Severín
+ PDF Chat	A Tabu Search Heuristic for the Equitable Coloring Problem	2014	Isabel Méndez Díaz Graciela Nasini Daniel Severín
+	New Bounds for the Nearly Equitable Edge Coloring Problem	2007	Xuzhen Xie Mutsunori Yagiura Takao Ono Tomio Hirata Uri Zwick
+	Equitable Coloring of Graphs	2013	Ko‐Wei Lih
+ PDF Chat	Total Equitable List Coloring	2018	Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer
+	Fast parallel algorithms for the approximate edge-coloring problem	1995	Weifa Liang
+	The Complexity of Equitable Vertex Coloring of Graphs	2005	Hanna Furmańczyk Marek Kubale
+	An exact algorithm for the edge coloring by total labeling problem	2018	Fabrizio Borghini Isabel Méndez‐Díaz Paula Zabala
+	Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture	2010	Henry A. Kiersteád Alexandr Kostochka
+ PDF Chat	Optimal Colorings with Rainbow Paths	2017	Oliver Bendele Dieter Rautenbach
+	Algorithms for weighted coloring problems	2017	Ram Sewak Dahal
+	A note on polynomial approximation of synchronizing optimal coloring	2011	Mikhail V. Berlinkov
+	Colorings at minimum cost	2009	Robert Berke Dieter Mitsche
+	Fast Algorithm for the Rainbow Disconnection Coloring of 2-Trees	2023	Xuqing Bai Li Bi Chuandong Xu Xin Zhang
+	Coloring Graphs with Minimal Edge Load	2004	Nitin Ahuja Andreas Baltz Benjamin Doerr Anand Srivastav
+	On Equitable Colorings of Sparse Graphs	2015	Xin Zhang
+	Equitable list tree-coloring of bounded treewidth graphs	2020	Yan Li Xin Zhang

Works That Cite This (73)

Action	Title	Year	Authors
+	Results about the total chromatic number and the conformability of some families of circulant graphs	2023	Luérbio Faria Mauro Nigro Myriam Preissmann Diana Sasaki
+	Edge-decompositions of graphs with high minimum degree	2015	Ben Barber Daniela Kühn Allan Lo Deryk Osthus
+	On the Corrádi-Hajnal Theorem and a question of Dirac	2016	H. A. Kierstead Alexandr Kostochka Elyse Yeager
+	A Ramsey-Turán theory for tilings in graphs	2021	Jie Han Patrick Morris Guanghui Wang Donglei Yang
+	Equitable Coloring of Graphs	2024	Ko‐Wei Lih
+	Equitable Coloring of Graphs	2013	Ko‐Wei Lih
+	Brooks's theorem	2015	Michael Stiebitz Bjarne Toft
+	Note on equitable colorings of graphs.	2014	T. Karthick
+	Approximate multipartite version of the Hajnal–Szemerédi theorem	2011	Béla Csaba Marcelo Mydlarz
+	Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs	2017	Hanna Furmańczyk Marek Kubale

Works Cited by This (10)

Action	Title	Year	Authors
+	Domain decomposition: Parallel multilevel methods for elliptic partial differential equations	1997	Barry Smith Petter E. Bjørstad William Gropp
+ PDF Chat	The infamous upper tail	2002	Svante Janson Andrzej Ruciński
+	Spanning subgraphs of random graphs	1992	Noga Alon Zoltán Füredi
+	Perfect Matchings in ϵ-Regular Graphs and the Blow-Up Lemma	1999	Vojtěch Rödl Andrzej Ruciński
+ PDF Chat	Ore-type graph packing problems	2006	Alexandr Kostochka Gexin Yu
+	Blow-up Lemma	1997	János Komlós Gábor N. Sárközy Endre Szemerédi
+ PDF Chat	An Ore-type theorem on equitable coloring	2007	H. A. Kierstead Alexandr Kostochka
+ PDF Chat	A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring	2007	H. A. Kierstead Alexandr Kostochka
+ PDF Chat	Ore-type versions of Brooks' theorem	2008	H. A. Kierstead Alexandr Kostochka
+	Combinatorial theory and its applications	1970	Colloquium on Combinatorial Theory P. Erdős Alfréd Rényi Vera T. Sós Bolyai János Matematikai Társulat