On coloring the arcs of biregular graphs

Abstract: Recalling each edge of a graph

H

has 2 oppositely oriented arcs, each vertex

v

of

H

is identified with the set of arcs, denoted

(v, e)

, departing from

v

along the edges

e

of

H

incident to

v

. Let

H

be a

(l a m b d a, m u)

-biregular graph with bipartition

(Y, X)

, where

| Y | = k m u

and

| X | = k l a m b d a

, (

0 < k, l a m b d a, m u i n m a t h b b Z

). We consider the problem, for each edge

e = y x

in

H

, of assigning, a color (given by an element) of

Y

, resp.

X

, to the arc

(y, e)

, resp.

(x, e)

, so that each color is assigned exactly once in the set of arcs departing from each vertex of

H

. Furthermore, we set such assignment to fulfill a specific bicolor weight function over a monotonic subset of

Y i m e s X

. This problem applies to the Design of Experiments for Industrial Chemistry, Molecular Biology, Cellular Neuroscience, etc. An algorithmic construction based on biregulzr graphs with bipartitions given by cyclic-group pairs is presented, as well as 3 essentially different solutions to the Great Circle Challenge Puzzle based on a different biregular graph whose bipartition is formed by the vertices and 5-cycles of the Petersen graph.

Recommendations

This page was built for publication: On coloring the arcs of biregular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777426)