2013/05/29 by R. R. Kamalian, Kamalian, R. R.
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1305.6866
4 pages
arxiv created 2013/05/29 · arxiv updated 2013/05/30
For an undirected, simple, finite, connected graph G, we denote by V(G) and E(G) the sets of its vertices and edges, respectively. A function φ:E(G)→\1,2,…,t\ is called a proper edge t-coloring of a graph G if adjacent edges are colored differently and each of t colors is used. An arbitrary nonempty subset of consecutive integers is called an interval. If φ is a proper edge t-coloring of a graph G and x∈ V(G), then SG(x,φ) denotes the set of colors of edges of G which are incident with x. A proper edge t-coloring φ of a graph G is called a cyclically-interval t-coloring if for any x∈ V(G) at least one of the following two conditions holds: a) SG(x,φ) is an interval, b) \1,2,…,t\∖ SG(x,φ) is an interval. For any t∈ ℕ, let \mathfrakMt be the set of graphs for which there exists a cyclically-interval t-coloring, and let \mathfrakM≡\bigcupt≥1\mathfrakMt. Examples of bipartite graphs that do not belong to the class \mathfrakM are constructed.