Research Papers

Home Publications Research Papers

Abstract: An odd coloring of a graph G is a proper coloring of G such that for every non-isolated vertex v, there is a color appearing an odd number of times in N-G(v). Odd coloring of graphs was studied intensively in recent few years. In this paper, we introduce the notion of a strong odd coloring, as not only a strengthened version of odd coloring, but also a relaxation of square coloring. A strong odd coloring of a graph G is a proper coloring of G such that for every non-isolated vertex v, if a color appears in N-G(v), then it appears an odd number of times in NG(v). We denote by chi(so)(G) the smallest integer k such that G admits a strong odd coloring with k colors. We prove that if G is a graph with mad(G) < (20)(7) , then chi(so)(G)

List