| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article forum
| |
|
Complexity of tree-coloring interval graphs equitably | Bei Niu
; Bi Li
; Xin Zhang
; | Date: |
9 Mar 2020 | Abstract: | An equitable tree-$k$-coloring of a graph is a vertex $k$-coloring such that
each color class induces a forest and the size of any two color classes differ
by at most one. In this work, we show that every interval graph $G$ has an
equitable tree-$k$-coloring for any integer $kgeq
lceil(Delta(G)+1)/2
ceil$, solving a conjecture of Wu, Zhang and Li (2013)
for interval graphs, and furthermore, give a linear-time algorithm for
determining whether a proper interval graph admits an equitable
tree-$k$-coloring for a given integer $k$. For disjoint union of split graphs,
or $K_{1,r}$-free interval graphs with $rgeq 4$, we prove that it is
$W[1]$-hard to decide whether there is an equitable tree-$k$-coloring when
parameterized by number of colors, or by treewidth, number of colors and
maximum degree, respectively. | Source: | arXiv, 2003.3945 | Services: | Forum | Review | PDF | Favorites |
|
|
No message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |