forgot password?
register here
Research articles
  search articles
  reviews guidelines
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
Members: 3431
Articles: 2'256'574
Articles rated: 2602

25 September 2022
  » arxiv » 2003.3945

 Article overview

Complexity of tree-coloring interval graphs equitably
Bei Niu ; Bi Li ; Xin Zhang ;
Date 9 Mar 2020
AbstractAn 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   
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
of broad interest:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser CCBot/2.0 (
» my Online CV
» Free

News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2022 - Scimetrica