Can I read Backbone colorings for graphs: Tree and path backbones on EtoBox?

Backbone colorings for graphs: Tree and path backbones by Hajo Broersma; Fedor V. Fomin; Petr A. Golovach; Gerhard J. Woeginger is a Computer Science article available to read on EtoBox.

What is Backbone colorings for graphs: Tree and path backbones about?

## Abstract We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph __G__ = (__V__,__E__) and a spanning subgraph __H__ of __G__ (the backbone of __G__), a backbone coloring for __G__ and __H__ is a proper vertex coloring __V__ → {1,2,...} of __G__ in which the colors assigned to adjacent vertices in __H__ differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of __G__ the number of colors needed for a backbone coloring of __G__ can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(__G__); for path backbones this factor is roughly ${{3}\over{2}}$. We show that the computational complexity of the problem “Given a graph __G__, a spanning tree __T__ of __G__, and an integer l, is there a backbone coloring for __G__ and __T__ with at most l colors?” jumps from polynomial to NP‐complete between l = 4 (easy for all spanning trees) and l = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007

Who reads Backbone colorings for graphs: Tree and path backbones?

Author

Hajo Broersma; Fedor V. Fomin; Petr A. Golovach; Gerhard J. Woeginger

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0364-9024)

Published

2007

Language

EN

Field

Computer Science (Physical Sciences)