On a conjecture by Plummer and Toft

The cyclic chromatic number χ_c(G) of a 2‐connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face‐bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3‐connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χ_c(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3‐connected plane graph, then χ_c>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999     

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

Fractional colorings with large denominators

The m-chromatic number χ_m(G) of a graph G is the fewest colors needed so each node has m colors and no color appears on adjacent nodes. The fractional chromatic number is χ*(G)=lim_m→∞χ_m(G)/m. Let m(G) be the least m so that χ* (G) = χ_m(G)/m. For n node graphs, Chvátal, Garey and Johnson showed m(G) ≦ n^n/2 and gave example, where m(G) is asymptotically . This note gives examples where m(G) is asymptotically λⁿ, where λ ≈? 1.346193. © 1995 John Wiley & Sons, Inc.     

A note on Ramsey numbers for books

The book with n pages B_n is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B_m,B_n) is the smallest integer r such that either B_m ? G or B_n ? G for every graph G of order r. We prove that there exists a positive constant c such that r(B_m,B_n) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory     

An improvement of the crossing number bound

The crossing number cr(G) of a simple graph G with n vertices and m edges is the minimum number of edge crossings over all drawings of G on the ?² plane. The conjecture made by Erd?s in 1973 that cr(G) ≥ Cm³/n² was proved in 1982 by Leighton with C = 1/100 and this constant was gradually improved to reach the best known value C = 1/31.08 obtained recently by Pach, Radoic?i?, Tardos, and Tóth [4] for graphs such that m ≥ 103n/16. We improve this result with values for the constant in the range 1/31.08 ≤ C &< 1/15 where C depends on m/n². For example, C > 1/25 for graphs with m/n² > 0.291 and n > 22, and C > 1/20 for dense graphs with m/n² ≥ 0.485. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

Circular choosability of graphs

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χ_{c, l}(G) of a graph G and prove that they are equivalent. Then we prove that for any graph G, χ_{c, l}(G) ≥ χ_l(G) ? 1. Examples are given to show that this bound is sharp in the sense that for any ? 0, there is a graph G with χ_{c, l}(G) > χ_l(G) ? 1 + ?. It is also proved that k‐degenerate graphs G have χ_{c, l}(G) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χ_{c, l}(G) ≥ 2k ? ?. This shows that χ_{c, l}(G) could be arbitrarily larger than χ_l(G). Finally we prove that if G has maximum degree k, then χ_{c, l}(G) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005     

On the complexity of the circular chromatic number

Circular chromatic number, χ_c is a natural generalization of chromatic number. It is known that it is NP ‐hard to determine whether or not an arbitrary graph G satisfies χ(G)=χ_c(G). In this paper we prove that this problem is NP ‐hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k ≥ 2 and n ≥ 3, for a given graph G with χ(G) = n, it is NP ‐complete to verify if . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004     

Further results on the lower bounds of mean color numbers

Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x₁,x₂,…,x_n such that x_i is contained in a K₃ of G[V_i] for i = 3,4,…,n, where V_i = {x₁,x₂,…,x_i}. This result improves two known results that μ(G) ≥ μ(O_n) where O_n is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005     

The Ramsey numbers for cycles versus wheels of odd order

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_n denote a cycle of order n and W_m a wheel of order m+1. It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that R(C_n,W_m)=2n−1 for even m≥4, n≥m and (n,m)≠(4,4). In this paper, we confirm the conjecture for n≥3m/2+1.     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

A ramsey-theoretic result involving chromatic numbers

The following result is proved. A graph G can be expressed as the edge-disjoint union of k graphs having chromatic numbers no greater than m₁,…,m_k, respectively, iff χ(G) ≤ m₁…m_k.     

Dirac type condition and Hamiltonian-connected graphs

Abstract

In 1952 Dirac introduced the Dirac type condition and proved that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ n/2, then G is Hamiltonian. In this paper we consider Hamiltonian-connectedness, which extends the Hamiltonian graphs and prove that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ (n ?1)/2, then G is Hamiltonian-connected or G belongs to five families of well-structured graphs. Thus, the condition and the result generalize the above condition and results of Dirac, respectively.     

Excluding Induced Subdivisions of the Bull and Related Graphs

For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph H, there is a function f_H: ?→? such that for every graph G∈Forb*(H), χ(G)≤f_H(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex‐disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Acyclic edge coloring of graphs with maximum degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

On stable crossing numbers

Results giving the exact crossing number of an infinite family of graphs on some surface are very scarce. In this paper we show the following: for G = Q_n × K_4.4, cr_y(G)-m(G) = 4m, for 0 ? = m ? 2ⁿ. A generalization is obtained, for certain repeated cartesian products of bipartite graphs. Nonorientable analogs are also developed.     

Circular flow numbers of regular multigraphs

The circular flow number F_c(G) of a graph G = (V, E) is the minimum r ϵ ℚ such that G admits a flow ϕ with 1 ≤ ϕ (e) ≤ r − 1, for each e ϵ E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t+1)‐regular graphs (t ≥ 1). Our results imply that there are gaps for possible circular flow numbers for (2t+1)‐regular graphs, e.g., there is no cubic graph G with 3 < F_c(G) < 4. We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 24–34, 2001