The circular chromatic number of series‐parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K₄‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K₅‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

On the vertex face total chromatic number of planar graphs

Let G be a planar graph. The vertex face total chromatic number _χ13(G) of G is the least number of colors assigned to V(G)∪F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for all outerplanar graphs and modulus 3-regular maximal planar graphs. (2) We prove that if G is a maximal planar graph or a lower degree planar graph, i.e., ∠(G) ≤ 3, then _χ13(G) ≤ 6. © 1996 John Wiley & Sons, Inc.     

Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

Let G(n,c/n) and G_r(n) be an n‐node sparse random graph and a sparse random r‐regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and G_r(n). The asymptotic value of I(n,c)/n as n → ∞, can be computed using the Karp‐Sipser algorithm when c ≤ e. For random cubic graphs, r = 3, it is only known that .432 ≤ lim inf_n I(n,3)/n ≤ lim sup_n I(n,3)/n ≤ .4591 with high probability (w.h.p.) as n → ∞, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649–664] and Bollabas [European J Combin 1 (1980), 311–316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit lim_n I(n,c)/n can be computed exactly even when c > e, and lim_n I(n,r)/n can be computed exactly for some r ≥ 1. For example, when the weights are exponentially distributed with parameter 1, lim_n I(n,2e)/n ≈ .5517, and lim_n I(n,3)/n ≈ .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n,c/n) and G_r(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r ≥ 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Circular flow on signed graphs

The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

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     

Balloons,cut‐edges,matchings, and total domination in regular graphs of odd degree

A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs with n vertices, and let ${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$. For ${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$, we prove the sharp inequalities c(G)?[r(n?2)?2]/(2r²+2r?1)?1 and α′(G)?n/2?rb/(2r+1). Using b?[(2r?1)n+2]/(4r²+4r?2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γ_t(G) of a cubic graph, we prove γ_t(G)?n/2?b(G)/2 (except that γ_t(G) may be n/2?1 when b(G)=3 and the balloons cover all but one vertex). With α′(G)?n/2?b(G)/3 for cubic graphs, this improves the known inequality γ_t(G)?α′(G). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010     

Some connected ramsey numbers

A graph G is co-connected if both G and its complement ? are connected and nontrivial. For two graphs A and B, the connected Ramsey number r_c(A, B) is the smallest integer n such that there exists a co-connected graph of order n, and if G is a co-connected graph on at least n vertices, then A ? G or B ? ?. If neither A or B contains a bridge, then it is known that r_c(A, B) = r(A, B), where r(A, B) denotes the usual Ramsey number of A and B. In this paper r_c(A, B) is calculated for some pairs (A, B) when r(A, B) is known and at least one of the graphs A or B has a bridge. In particular, r_c(A, B) is calculated for A a path and B either a cycle, star, or complete graph, and for A a star and B a complete graph.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Relationships between total domination,order, size,and maximum degree of graphs

A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γ_t(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6 , it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γ_t(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γ_t(G))/2 holds. In this article, we prove that holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γ_t(G))/2. The last result also disproves a conjecture on domination numbers from 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Unexpected behaviour of crossing sequences

The nth crossing number of a graph G, denoted ncr(G), is the minimum number of crossings in a drawing of G on an orientable surface of genus n. We prove that for every a>b>0, there exists a graph G for which ₀cr(G)=a, ₁cr(G)=b, and ₂cr(G)=0. This provides support for a conjecture of Archdeacon et al. and resolves a problem of Salazar.