Equitable colorings of bounded treewidth graphs

DOI10.1016/j.tcs.2005.09.027zbMath1086.68096OpenAlexW2140465653WikidataQ59567836 ScholiaQ59567836MaRDI QIDQ817768

Hans L. Bodlaender, Fedor V. Fomin

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.027

zbMATH Keywords

treewidthequitable coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

Iterated Type Partitions ⋮ On equitable colouring of Knödel graphs ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ Equitable colorings of corona multiproducts of graphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ A STUDY ON EQUITABLE CHROMATIC AND THRESHOLD OF MYCIELSKIAN OF GRAPHS ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Complexity aspects of restrained Roman domination in graphs ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ Scheduling with machine conflicts ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Equitable coloring on total graph of bigraphs and central graph of cycles and paths ⋮ Partitioning graphs into induced subgraphs ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Locally boundedk-colorings of trees ⋮ Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms ⋮ On Equitable Coloring of Central Graphs and Total Graphs ⋮ Decomposition, reformulation, and diving in university course timetabling ⋮ On the equitable choosability of the disjoint union of stars

Cites Work

• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• A note on the decomposition of graphs into isomorphic matchings
• An existential problem of a weight-controlled subset and its application to school timetable construction
• Chromatic optimisation: Limitations, objectives, uses, references
• Equitable and proportional coloring of trees
• NP-completeness of graph decomposition problems
• Equitable coloring of trees
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Edge dominating set and colorings on graphs with fixed clique-width
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Complexity Results for Bandwidth Minimization
• The χt-coloring problem
• The $L(2,1)$-Labeling Problem on Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• On Equitable Coloring of d-Degenerate Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Automata, Languages and Programming
• Bounded vertex coloring of trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Equitable colorings of bounded treewidth graphs