Block graphs - some general results and their equitable colorings
Preprint
Abstract
In this paper, we consider some general properties of block graphs as well as the equitable coloring problem in this class of graphs. In the first part we establish the relation between two structural parameters for general block graphs. We also give complete characterization of block graphs with given value of parameter $α_{\min}$. In the next part of the paper we confirm the hypothesis for some subclass of GLS block graphs in which the problem of EQUITABLE COLORING is unlikely to be polynomial time solvable. We give also an equitable $(n+2)$-algorithm for all GLS block graphs. As a by product we prove that the equitable chromatic spectrum for the subclass of GLS block graphs is gap-free.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Proof of the Goldberg–Seymour conjecture on edge–colorings of multigraphsJournal of Combinatorial Optimization, 2025
- Gap one bounds for the equitable chromatic number of block graphsDiscrete Applied Mathematics, 2023
- Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and KernelizationAlgorithmica, 2022
- Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machinesDiscrete Applied Mathematics, 2018
- Algorithmic Meta-theorems for Restrictions of TreewidthAlgorithmica, 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 note on equitable colorings of forestsEuropean Journal of Combinatorics, 2009
- Equitable colorings of bounded treewidth graphsTheoretical Computer Science, 2005
- Restrictions of graph partition problems. Part ITheoretical Computer Science, 1995