Some Results On Minimally Circular-Imperfect Graphs

For two integers 1 ≤ d ≤ k,a k/d-circular coloring of a graph G is a mapping c : V(G) → {0,1... k — 1} such that d v |c(u) — c(v)| ≤ k — d whenever uv ∈ E(G). The circular chromatic number of G, denoted by X_c(G), is the least rational number k/d such that there is a k/d-circular coloring of G. The circular clique number of a graph G, denoted by ω(G), is the maximum rational number k/d such that K_k/d admits a homomorphism to G. A graph G is called a circular-perfect graph if ω_c(H) = X_c(H) for each induced subgraph H of G. A graph is minimally circular-imperfect if it is not circular-perfect but each of its proper induced subgraphs is. Minimally circular-imperfect graph is used to study the structure of circular-perfect graph and it seems that the structure of minimally circular-imperfect graphs is very complicated. In this paper, we discover that some flowers under certain conditions are minimally circular-imperfect. And several families of minimally circular-imperfect graphs are constructed from K_k/d, one of which is constructed by deleting an edge from K_k/d. Butthe operation is not always successful, so some results are given in the paper. At the end, we guess that G = K_k/d\e for e 6 K_k/d is notminimally circular-imperfet, if ω_c(G) = X_c(G) or G contains a proper induced subgraph H that is not circualr-perfect, and H is the min-...