Equitable List Coloring of Graphs with Bounded Degree

A graph G is equitably k‐choosable if for every k‐list assignment L there exists an L‐coloring of G such that every color class has at most vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably ‐choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r³ vertices is equitably ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.     

Coloring Cubic Graphs by Point‐Intransitive Steiner Triple Systems

An ‐coloring of a cubic graph G is an edge coloring of G by points of a Steiner triple system such that the colors of any three edges meeting at a vertex form a block of . A Steiner triple system that colors every simple cubic graph is said to be universal. It is known that every nontrivial point‐transitive Steiner triple system that is neither projective nor affine is universal. In this article, we present the following results.

相似文献   

Partial Online List Coloring of Graphs

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s‐choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s‐choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s‐choosable and , then and for any , .     

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

Upper bound involving parameter σ 2 for the rainbow connection number

Let G be a connected graph of order n. The rainbow connection number rc（G） of G was introduced by Chartrand et al. Chandran et al. used the minimum degree of G and obtained an upper bound that rc（G） 〈_ 3n/（ δ＋ 1） - 3, which is tight up to additive factors. In this paper, we use the minimum degree-sum a2 6n of G to obtain a better bound rc（G） _〈 - 8, especially when is small （constant） but a2 is large （linear in n）.     

被积函数正负性周期变化的反常积分

从被积函数的正负性变化规律入手,借助交错级数的敛散性,给出并证明相应反常积分的敛散性,进而推广得出一类反常积分的敛散性判定定理．     

Completions of ‐Dense Partial Latin Squares

A classical question in combinatorics is the following: given a partial Latin square P, when can we complete P to a Latin square L? In this paper, we investigate the class of ε‐dense partial Latin squares: partial Latin squares in which each symbol, row, and column contains no more than ‐many nonblank cells. Based on a conjecture of Nash‐Williams, Daykin and Häggkvist conjectured that all ‐dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this technique to study ε‐dense partial Latin squares that contain no more than filled cells in total. In this paper, we construct completions for all ε‐dense partial Latin squares containing no more than filled cells in total, given that . In particular, we show that all ‐dense partial Latin squares are completable. These results improve prior work by Gustavsson, which required , as well as Chetwynd and Häggkvist, which required , n even and greater than 10⁷.     

Backbone colorings for graphs: Tree and path backbones

We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex coloring V → {1,2,…} of G in which the colors assigned to adjacent vertices in H differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of G the number of colors needed for a backbone coloring of G can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(G); for path backbones this factor is roughly . We show that the computational complexity of the problem “Given a graph G, a spanning tree T of G, and an integer ?, is there a backbone coloring for G and T with at most ? colors?” jumps from polynomial to NP‐complete between ? = 4 (easy for all spanning trees) and ? = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

The adaptable choosability number grows with the choosability number

The adaptable choosability number of a multigraph G, denoted ch_a(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that ch_a grows with ch, i.e. there is a function f tending to infinity such that ch_a(G)≥f(ch(G)).