Equitable colorings of bounded treewidth graphs

Hans L. Bodlaender, Fedor V. Fomin

Type: Article

Publication Date: 2005-10-05

Citations: 72

DOI: https://doi.org/10.1016/j.tcs.2005.09.027

View Publication

Locations

Utrecht University Repository (Utrecht University) - View - PDF
Theoretical Computer Science - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Equitable Colorings of Bounded Treewidth Graphs	2004	Hans L. Bodlaender Fedor V. Fomin
+	Parameterized Complexity of Equitable Coloring	2019	Guilherme C. M. Gomes Carlos V. G. C. Lima Vinícius Fernandes dos Santos
+	Parameterized Complexity of Equitable Coloring	2019	Guilherme C. M. Gomes Carlos V. G. C. Lima Vinícius Fernandes dos Santos
+	Parameterized Complexity of Equitable Coloring	2018	Guilherme C. M. Gomes Carlos V. G. C. Lima Vinícius F. dos Santos
+ PDF Chat	Equitable Coloring of Sparse Planar Graphs	2010	Rong Luo Jean‐Sébastien Sereni Diane Stephens Gexin Yu
+ PDF Chat	Complexity of Tree-Coloring Interval Graphs Equitably	2020	Bei Niu Li Bi Xin Zhang
+	Complexity of tree-coloring interval graphs equitably	2020	Bei Niu Li Bi Xin Zhang
+ PDF Chat	On the Complexity of Some Colorful Problems Parameterized by Treewidth	2007	Michael R. Fellows Fedor V. Fomin Daniel Lokshtanov Frances Rosamond Saket Saurabh Stefan Szeider Carsten Thomassen
+	Complexity of equitable tree-coloring problems	2016	Keaitsuda Maneeruk Nakprasit Kittikorn Nakprasit
+	Equitable colorings of complete multipartite graphs	2015	Keaitsuda Maneeruk Nakprasit Kittikorn Nakprasit
+	Equitable list coloring and treewidth	2009	Michael J. Pelsmajer
+	Equitable chromatic threshold of complete multipartite graphs	2012	Zhidan Yan Wei Wang
+	Equitable Coloring of Trees	1994	Bor‐Liang Chen Ko‐Wei Lih
+	On equitable <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>Δ</mml:mi></mml:math>-coloring of graphs with low average degree	2005	Alexandr Kostochka Kittikorn Nakprasit
+	Total Equitable List Coloring	2018	Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer
+	Total Equitable List Coloring	2018	Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer
+ PDF Chat	A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring	2007	H. A. Kierstead Alexandr Kostochka
+	Equitable Coloring of Graphs with Intermediate Maximum Degree	2014	Bor-Liang Chen Kuo‐Ching Huang Ko‐Wei Lih
+	Equitable Partition of Graphs into Independent Sets and Cliques	2019	Bruno B. Monteiro Vinicius dos Santos
+ PDF Chat	An Ore-type theorem on equitable coloring	2007	H. A. Kierstead Alexandr Kostochka

Works That Cite This (38)

Action	Title	Year	Authors
+	Equitable Coloring On Mycielskian Of Wheels And Bigraphs	2013	K. Kaliraj J. Vernold Vivin Akbar Ali Mohamed Moideen
+ PDF Chat	On the Complexity of Some Colorful Problems Parameterized by Treewidth	2007	Michael R. Fellows Fedor V. Fomin Daniel Lokshtanov Frances Rosamond Saket Saurabh Stefan Szeider Carsten Thomassen
+	Equitable Coloring of Graphs	2024	Ko‐Wei Lih
+	Equitable Coloring of Graphs	2013	Ko‐Wei Lih
+ PDF Chat	The Equitable Chromatic Bounds on Splitting of Block Circulant Graphs	2022	M Jagannathan J. Vernold Vivin Veninstine Vivik.J
+	Iterated Type Partitions	2020	Gennaro Cordasco Luisa Gargano Adele A. Rescigno
+	Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees	2019	Cédric Bentz
+	Parameterized complexity for iterated type partitions and modular-width	2024	Gennaro Cordasco Luisa Gargano Adele A. Rescigno
+	On equitable colouring of Knödel graphs	2013	K. Kaliraj J. Vernold Vivin Mohammed Ali
+	Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and Kernelization	2022	Guilherme C. M. Gomes Matheus R. Guedes Vinícius Fernandes dos Santos

Works Cited by This (9)

Action	Title	Year	Authors
+	Domain decomposition: Parallel multilevel methods for elliptic partial differential equations	1997	Barry Smith Petter E. Bjørstad William Gropp
+	Equitable and m-bounded coloring of split graphs	1996	Bor-Liang Chen Ming‐Tat Ko Ko‐Wei Lih
+	Equitable Coloring of Trees	1994	Bor‐Liang Chen Ko‐Wei Lih
+	Equitable and proportional coloring of trees	1983	Béla Bollobás Richard K. Guy
+	On complexity of some chain and antichain partition problems	1992	Zbigniew Lonc
+	NP-Completeness of graph decomposition problems	1991	Edith Cohen Michael Tarsi
+	Edge dominating set and colorings on graphs with fixed clique-width	2002	Daniel Kobler Udi Rotics
+ PDF Chat	On Equitable Coloring of <i>d</i>-Degenerate Graphs	2005	Alexandr Kostochka Kittikorn Nakprasit Sriram V. Pemmaraju
+	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