Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
Preprint
Abstract
An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of $G$, such that the sizes of any two color classes differ by at most one. In this paper, we consider the equitable coloring problem in block graphs. Recall that the latter are graphs in which each 2-connected component is a complete graph. The problem remains hard in the class of block graphs. In this paper, we present some graph theoretic results relating various parameters. Then we use them in order to trace some algorithmic implications, mainly dealing with the fixed-parameter tractability of the problem.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphsDiscrete Applied Mathematics, 2018
- Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machinesDiscrete Applied Mathematics, 2018
- A DSATUR-based algorithm for the Equitable Coloring ProblemComputers & Operations Research, 2015
- Bin packing with fixed number of bins revisitedJournal of Computer and System Sciences, 2013
- Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐ColoringJournal of Graph Theory, 2011
- Parameterized complexity of coloring problems: Treewidth versus vertex coverTheoretical Computer Science, 2011
- On the complexity of some colorful problems parameterized by treewidthInformation and Computation, 2011
- A fast algorithm for equitable coloringCombinatorica, 2010
- Heuristics and lower bounds for the bin packing problem with conflictsComputers & Operations Research, 2004
- Restrictions of graph partition problems. Part ITheoretical Computer Science, 1995