Decomposable symmetric designs

The first infinite families of symmetric designs were obtained from finite projective geometries, Hadamard matrices, and difference sets. In this paper we describe two general methods of constructing symmetric designs that give rise to the parameters of all other known infinite families of symmetric designs. The method of global decomposition produces an incidence matrix of a symmetric design as a block matrix with each block being a zero matrix or an incidence matrix of a smaller symmetric design. The method of local decomposition represents incidence matrices of a residual and a derived design of a symmetric design as block matrices with each block being a zero matrix or an incidence matrix of a smaller residual or derived design, respectively.     

Improper choosability of graphs and maximum average degree

Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer g_k such that every planar graph of girth at least g_k is k‐improper 2‐choosable. He proved [9] that 6 ≤ g₁ ≤ 9; 5 ≤ g₂ ≤ 7; 5 ≤ g₃ ≤ 6; and ? k ≥ 4, g_k = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then . As a corollary, we deduce that g₁ ≤ 8 and g₂ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006     

Using graphs for some discrete tomography problems

Given a rectangular array whose entries represent the pixels of a digitalized image, we consider the problem of reconstructing an image from the number of occurrences of each color in every column and in every row. The complexity of this problem is still open when there are just three colors in the image. We study some special cases where the number of occurrences of each color is limited to small values. Formulations in terms of edge coloring in graphs and as timetabling problems are used; complexity results are derived from the model.     

Coloring mixed hypertrees

A mixed hypergraph is a triple (V,C,D) where V is its vertex set and C and D are families of subsets of V, called C-edges and D-edges, respectively. For a proper coloring, we require that each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all k's for which there exists a proper coloring using exactly k colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree.We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by k colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

A sufficient condition for planar graphs to be acyclically 5‐choosable

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Smaller planar triangle-free graphs that are not 3-list-colorable

In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

Regular Balanced Cayley Maps for Cyclic, Dihedral and Generalized Quaternion Groups

A Cayley map is a Cayley graph embedded in an orientable surface such that. the local rotations at every vertex are identical. In this paper, balanced regular Cayley maps for cyclic groups, dihedral groups, and generalized quaternion groups are classified.     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．