The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own l...The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own listno matter whatthe lists are.In this paper,itis showed thatχl(G)≤ 3 for each plane graph of girth not less than 4 which contains no 6- ,7- and 9- cycles展开更多
An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analo...An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.展开更多
基金supported by the National Natural Science Foundation of China(1 0 0 0 1 0 35)
文摘The choice number of a graph G,denoted byχl(G) ,is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own listno matter whatthe lists are.In this paper,itis showed thatχl(G)≤ 3 for each plane graph of girth not less than 4 which contains no 6- ,7- and 9- cycles
基金This research is supported partially by National Natural Science Funds of China(10001035 and 10371055).
文摘An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.
