Paper Image

Total coloring via efficient dominating sets

Published on:

14 May 2024

Primary Category:


Paper Authors:

Italo J. Dejter


Key Details

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

AI generated summary

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.

Answers from this paper


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

Sign up to comment on this paper

Sign Up