Visibility Graphs of Point Sets in the Plane

The visibility graph of a discrete point set X⊂ℝ² has vertex set X and an edge xy for every two points x,y∈X whenever there is no other point in X on the line segment between x and y. We show that for every graph G, there is a point set X∈ℝ², such that the subgraph of induced by X is isomorphic to G. As a consequence, we show that there are visibility graphs of arbitrary high chromatic number with clique number 6 settling a question by Kára, Pór and Wood. Supported by the DFG Research Center Matheon (FZT86).     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

Clique coloring of binomial random graphs

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.     

Coloring the cliques of line graphs

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals $2$ is NP-complete. We deal with the CCHN of the graph itself as well.     

List-Coloring Claw-Free Graphs with Small Clique Number

Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.     

Computing clique and chromatic number of circular-perfect graphs in polynomial time

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function.     

图K_(2n)\E(F_4)(n≥12)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果.f满足:1)对任意的uv,uw∈E(G),v≠w,有.f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}.研究了图K_(2n)\E(F_4)(n≥12)的点可区别边色数.     

On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

Permutation diagrams have been used in circuit design to model a set of single point nets crossing a channel, where the minimum number of layers needed to realize the diagram equals the clique number ω(G) of its permutation graph, the value of which can be calculated in O(nlogn) time. We consider a generalization of this model motivated by “standard cell” technology in which the numbers on each side of the channel are partitioned into consecutive subsequences, or cells, each of which can be left unchanged or flipped (i.e., reversed). We ask, for what choice of flippings will the resulting clique number be minimum or maximum. We show that when one side of the channel is fixed (no flipping), an optimal flipping for the other side can be found in O(nlogn) time for the maximum clique number, and that when both sides are free this can be solved in O(n²) time. We also prove NP-completeness of finding a flipping that gives a minimum clique number, even when one side of the channel is fixed, and even when the size of the cells is restricted to be less than a small constant. Moreover, since the complement of a permutation graph is also a permutation graph, the same complexity results hold for the stable set (independence) number. In the process of the NP-completeness proof we also prove NP-completeness of a restricted variant of a scheduling problem. This new NP-completeness result may be of independent interest.     

Pm×Kn的邻点可区别全色数

设G是简单图．设f是一个从V(G)∪E(G)到{1,2,…,k}的映射．对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}．如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC)．数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数．本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数．     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

关于偏序集相关联图的色数

对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.     

Covering the vertex set of a graph with subgraphs of smaller degree

The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum.     

Computing the maximum clique in the visibility graph of a simple polygon

In this paper, we present an algorithm for computing the maximum clique in the visibility graph G of a simple polygon P in O(n²e) time, where n and e are number of vertices and edges of G respectively. We also present an O(ne) time algorithm for computing the maximum hidden vertex set in the visibility graph G of a convex fan P. We assume in both algorithms that the Hamiltonian cycle in G that corresponds to the boundary of P is given as an input along with G.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

一类3-正则图的邻强边染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv,uw∈E(G),u≠w,f(uv)≠f(uw);(2)uv∈E(G),C(u)≠C(v).则称f是G的一个邻强边染色,最小的k称为邻强边色数,其中C(u)={f(uv)|uv∈E(G)}.给出了一类3-正则重圈图的邻强边色数.     

Some Theorems Concerning the Star Chromatic Number of a Graph

We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number.     

New Results on the Queens_n 2 Graph Coloring Problem

For the Queens_n ² graph coloring problems no chromatic numbers are available for n > 9 except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14.     

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.