
arXiv: 2009.12784
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.
FOS: Computer and information sciences, block-graph, equitable coloring, Discrete Mathematics (cs.DM), mathematics - combinatorics, 05C15, 05C85, 68R10, W[1]-hardness, computer science - discrete mathematics, fixed-parameter tractability, QA1-939, FOS: Mathematics, 05c15, 05c85, 68r10, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, block-graph, equitable coloring, Discrete Mathematics (cs.DM), mathematics - combinatorics, 05C15, 05C85, 68R10, W[1]-hardness, computer science - discrete mathematics, fixed-parameter tractability, QA1-939, FOS: Mathematics, 05c15, 05c85, 68r10, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
