New results about set colorings of graphs (Q612965)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5827422
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | New results about set colorings of graphs |
scientific article; zbMATH DE number 5827422 |
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
0.8423623442649841
0 references
0.8404186964035034
0 references
0.8226155042648315
0 references
0.8042374849319458
0 references
