Geodesic
Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
Discrete mathematics & theoretical computer science, special issue in honour of Maurice Pouzet, Tome 23 (2021-2022) no. 2.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.6860
Classification : 05C15, 05C85, 68R10 
@article{DMTCS_2022_23_2_a6,
     author = {Furma\'nczyk, Hanna and Mkrtchyan, Vahan},
     title = {Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2021-2022},
     doi = {10.46298/dmtcs.6860},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6860/}
}
TY  - JOUR
AU  - Furmańczyk, Hanna
AU  - Mkrtchyan, Vahan
TI  - Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6860/
DO  - 10.46298/dmtcs.6860
LA  - en
ID  - DMTCS_2022_23_2_a6
ER  - 
%0 Journal Article
%A Furmańczyk, Hanna
%A Mkrtchyan, Vahan
%T Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6860/
%R 10.46298/dmtcs.6860
%G en
%F DMTCS_2022_23_2_a6
Furmańczyk, Hanna; Mkrtchyan, Vahan. Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs. Discrete mathematics & theoretical computer science, special issue in honour of Maurice Pouzet, Tome 23 (2021-2022) no. 2. doi : 10.46298/dmtcs.6860. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6860/

Cité par Sources :