Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings

Abstract: Let

H

be a graph with

D e l t a (H) l e q 2

, and let

G

be obtained from

H

by gluing in vertex-disjoint copies of

K_{4}

. We prove that if

H

contains at most one odd cycle of length exceeding

3

, or if

H

contains at most

3

triangles, then

c h i (G) l e q 4

. This proves the Strong Coloring Conjecture for such graphs

H

. For graphs

H

with

D e l t a = 2

that are not covered by our theorem, we prove an approximation result towards the conjecture.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings