Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » 2194064

 Article forum


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   
 

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..

Subject of your forum message:
Write your forum message below (min 50, max 2000 characters)

2000 characters left.
Please, read carefully your message since you cannot modify it after submitting.

  To add a message in the forum, you need to login or register first. (free): registration page






ScienXe.org
» my Online CV
» Free


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