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)).     

On lower bounds for the chromatic number in terms of vertex degree

In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K_1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K_2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in [S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11].     

A note on the monotonicity of mixed Ramsey numbers

For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of K_n is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge.     

The incidence game chromatic number of paths and subgraphs of wheels

The incidence game chromatic number was introduced to unify the ideas of the incidence coloring number and the game chromatic number. We determine the exact incidence game chromatic number of large paths and give a correct proof of a result stated by Andres [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009) 1980-1987] concerning the exact incidence game chromatic number of large wheels.     

A structural theorem for planar graphs with some applications

In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Three new upper bounds on the chromatic number

This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, ξ, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas ζ and η are based on the degree of the nodes in the graph. The computation complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.