Odd-sum colorings of planar graphs

Abstract: A emph{coloring} of a graph

G

is a map

f : V (G) o m a t h b b Z^{+}

such that

f (v) e f (w)

for all

v w i n E (G)

. A coloring

f

is an emph{odd-sum} coloring if

s u m_{w i n N [v]} f (w)

is odd, for each vertex

v i n V (G)

. The emph{odd-sum chromatic number} of a graph

G

, denoted

c h i_{o s} (G)

, is the minimum number of colors used (that is, the minimum size of the range) in an odd-sum coloring of

G

. Caro, Petruv{s}evski, and v{S}krekovski showed, among other results, that

c h i_{o s} (G)

is well-defined for every finite graph

G

and, in fact,

c h i_{o s} (G) l e 2 c h i (G)

. Thus,

c h i_{o s} (G) l e 8

for every planar graph

G

(by the 4 Color Theorem),

c h i_{o s} (G) l e 6

for every triangle-free planar graph

G

(by Gr"{o}tzsch's Theorem), and

c h i_{o s} (G) l e 4

for every bipartite planar graph. Caro et al. asked, for every even

D e l t a g e 4

, whether there exists

g_{D e l t a}

such that if

G

is planar with maximum degree

D e l t a

and girth at least

g_{D e l t a}

then

c h i_{o s} (G) l e 5

. They also asked, for every even

D e l t a g e 4

, whether there exists

g_{D e l t a}

such that if

G

is planar and bipartite with maximum degree

D e l t a

and girth at least

g_{D e l t a}

then

c h i_{o s} (G) l e 3

. We answer both questions negatively. We also refute a conjecture they made, resolve one further problem they posed, and make progress on another.

Recommendations

Cites Work

This page was built for publication: Odd-sum colorings of planar graphs