REAL

Maximum number of colors in hypertrees of bounded degree

Bujtás, Csilla and Tuza, Zsolt (2015) Maximum number of colors in hypertrees of bounded degree. Central European Journal of Operations Research, 23 (4). pp. 867-786. ISSN 1435-246X

[img]
Preview
Text
C_htree_boundeddegreeR_u.pdf

Download (110kB) | Preview

Abstract

The upper chromatic number (Formula presented.) of a hypergraph (Formula presented.) is the maximum number of colors that can occur in a vertex coloring (Formula presented.) such that no edge (Formula presented.) is completely multicolored. A hypertree (also called arboreal hypergraph) is a hypergraph whose edges induce subtrees on a fixed tree graph. It has been shown that on hypertrees it is algorithmically hard not only to determine exactly but also to approximate the value of (Formula presented.), unless (Formula presented.). In sharp contrast to this, here we prove that if the input is restricted to hypertrees (Formula presented.) of bounded maximum vertex degree, then (Formula presented.) can be determined in linear time if an underlying tree is also given in the input. Consequently, (Formula presented.) on hypertrees is fixed parameter tractable in terms of maximum degree. © 2014 Springer-Verlag Berlin Heidelberg.

Item Type: Article
Uncontrolled Keywords: Vertex coloring; Upper chromatic number; hypertree; Hypergraph; C-coloring; Arboreal hypergraph
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 17 Feb 2016 07:56
Last Modified: 17 Feb 2016 07:56
URI: http://real.mtak.hu/id/eprint/33603

Actions (login required)

Edit Item Edit Item