Ramsey-goodness—and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r _Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r _Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r _Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r _Δ > 2 ^cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r _Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P _n ^k , the kth power of a path P _n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K ₃) > cn. We show that, given Δ and H, there are β>0 and n ₀ such that, if G is a connected graph on n≥n ₀ vertices with maximum degree at most Δ and bandwidth at most β _n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn.     

On embedding well-separable graphs

Call a simple graph H of order nwell-separable, if by deleting a separator set of size o(n) the leftover will have components of size at most o(n). We prove, that bounded degree well-separable spanning subgraphs are easy to embed: for every γ>0 and positive integer Δ there exists an n₀ such that if n>n₀, Δ(H)?Δ for a well-separable graph H of order n and δ(G)?(1-1/2(χ(H)-1)+γ)n for a simple graph G of order n, then H⊂G. We extend our result to graphs with small band-width, too.     

Some results on the spectral radii of bicyclic graphs

A bicyclic graph is a connected graph in which the number of edges equals the number of vertices plus one. Let Δ(G) and ρ(G) denote the maximum degree and the spectral radius of a graph G, respectively. Let B(n) be the set of bicyclic graphs on n vertices, and B(n,Δ)={G∈B(n)∣Δ(G)=Δ}. When Δ≥(n+3)/2 we characterize the graph which alone maximizes the spectral radius among all the graphs in B(n,Δ). It is also proved that for two graphs G₁ and G₂ in B(n), if Δ(G₁)>Δ(G₂) and Δ(G₁)≥⌈7n/9⌉+9, then ρ(G₁)>ρ(G₂).     

On equality in an upper bound for the restrained and total domination numbers of a graph

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_t(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γ_r(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γ_t(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γ_t(G)=n-Δ.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

The Chromatic Index of a Graph Whose Core is a Cycle of Order at Most 13

Let G be a graph. The core of G, denoted by G _Δ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) denotes the maximum degree of G. A k -edge coloring of G is a function f : E(G) → L such that |L| = k and f (e ₁) ≠ f (e ₂) for all two adjacent edges e ₁ and e ₂ of G. The chromatic index of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G) = Δ(G) and Class 2 if χ′(G) = Δ(G) + 1. In this paper it is shown that every connected graph G of even order whose core is a cycle of order at most 13 is Class 1.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

Variable neighborhood search for extremal graphs. 23. On the Randi? index and the chromatic number

Let G=(V,E) be a simple graph with vertex degrees d₁,d₂,…,d_n. The Randi? index R(G) is equal to the sum over all edges (i,j)∈E of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(G). To prove it, we also show that if v∈V is a vertex of minimum degree δ of G, G−v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G, then .     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.     

The edge-face coloring of graphs embedded in a surface of characteristic zero

Let G be a graph embedded in a surface of characteristic zero with maximum degree Δ. The edge-face chromatic number χ_ef(G) of G is the least number of colors such that any two adjacent edges, adjacent faces, incident edge and face have different colors. In this paper, we prove that χ_ef(G)≤Δ+1 if Δ≥13, χ_ef(G)≤Δ+2 if Δ≥12, χ_ef(G)≤Δ+3 if Δ≥4, and χ_ef(G)≤7 if Δ≤3.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Theorems on matroid connectivity

It is proved that for every k?4 there is a Δ(k) such that for every g there is a graph G with maximal degree at most Δ(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to Δ(k) does not seem to slow down the growth of the maximal girth of a k-chromatic graph of order n as n → ∞.     

The total chromatic number of Pseudo-Halin graphs with lower degree

The total chromatic number χ_T(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident elements receive the same color. The Total Coloring Conjecture(TCC) states that for every simple graph G, χ_T(G)≤Δ(G)+2. In this paper, we show that χ_T(G)=Δ(G)+1 for all pseudo-Halin graphs with Δ(G)=4 and 5.     

Injective coloring of planar graphs

A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχ_i(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χ_i(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χ_i(G)≤Δ+1 if g≥11; (3) χ_i(G)≤Δ+2 if g≥8.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.