New results about set colorings of graphs (Q612965)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New results about set colorings of graphs |
scientific article |
Statements
New results about set colorings of graphs (English)
0 references
16 December 2010
0 references
Summary: The set coloring problem is a new kind of both vertex and edge coloring of a graph introduced by Suresh Hegde in 2009 [\textit{S.M. Hegde}, ``Set colorings of graphs,'' Eur. J. Comb. 30, No.\,, 986--995 (2009; Zbl 1198.05051)]. 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.
0 references
set coloring problem
0 references
vertex coloring
0 references
edge coloring
0 references
paths
0 references
binary trees
0 references
Latin squares
0 references
strong set coloring
0 references