New Results about Set Colorings of Graphs

The set coloring problem is a new kind of both vertex and edge coloring of a graph introduced by Suresh Hegde in 2009. Only large bounds have been given on the chromatic number for general graphs. In this paper, we consider the problem on paths and complete binary trees, and show that it can be redu...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2010-12, Vol.17 (1)
Main Authors: Boutin, J. P., Duchêne, E., Effantin, B., Kheddouci, H., Seba, H.
Format: Article
Language:English
Subjects:
Combinatorics
Mathematics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The set coloring problem is a new kind of both vertex and edge coloring of a graph introduced by Suresh Hegde in 2009. Only large bounds have been given on the chromatic number for general graphs. In this paper, we consider the problem on paths and complete binary trees, and show that it can be reduced to the computation of a transversal in a special Latin square, i.e., the XOR table. We then investigate a variation of the problem called strong set coloring, and we provide an exhaustive list of all graphs being strongly set colorable with at most 4 colors.
ISSN:1077-8926
1077-8926
DOI:10.37236/445