Published on:

14 May 2024

Primary Category:

Combinatorics

Paper Authors:

Italo J. Dejter

•

Proves 3-cube graph has totally efficient 4-coloring with vertex color classes as efficient dominating sets

•

Conjectures 3-cube is only such case of totally effective coloring

•

Relates to edge-girth colorings of prism graphs of star transposition graphs

•

Shows totally efficient colorings can yield orthogonal 1-factorizations

•

Extends 3-cube efficient coloring to produce edge-girth 4-cube coloring

Total coloring via efficient dominating sets

This paper studies total colorings of graphs where each vertex color class forms an efficient dominating set, meaning a minimal set that is within 1 edge of every vertex. It proves the 3-cube graph has such a coloring using 4 colors, and conjectures this is the only such case. It relates this to edge colorings of prism graphs formed from star transposition graphs.

No comments yet, be the first to start the conversation...

Sign up to comment on this paper