Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable

The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ’’ (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ’’ (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ’’(G) = 9.     

Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers

Let G be a graph of nonnegative characteristic and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (1) Δ(H)?1 if g(G)?11; (2) Δ(H)?2 if g(G)?7; (3) Δ(H)?4 if either g(G)?5 or G does not contain 4-cycles and 5-cycles; (4) Δ(H)?6 if G does not contain 4-cycles. These results are applied to find the following upper bounds for the game coloring number col_g(G) of G: (1) col_g(G)?5 if g(G)?11; (2) col_g(G)?6 if g(G)?7; (3) col_g(G)?8 if either g(G)?5 or G contains no 4-cycles and 5-cycles; (4) col_g(G)?10 if G does not contain 4-cycles.     

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ’a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ’a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.     

Convergence of Gaussian Quadrature Formulas for Power Orthogonal Polynomials

In classical theorems on the convergence of Gaussian quadrature formulas for power orthogonal polynomials with respect to a weight w on I =（a,b）,a function G ∈ S（w）:= { f:∫_I | f（x）| w（x）d x < ∞} satisfying the conditions G ^2j（x） ≥ 0,x ∈（a,b）,j = 0,1,...,and growing as fast as possible as x → a + and x → b,plays an important role.But to find such a function G is often difficult and complicated.This implies that to prove convergence of Gaussian quadrature formulas,it is enough to find a function G ∈ S（w） with G ≥ 0 satisfying sup n ∑λ0knG（xkn） k=1 n<∞ instead,where the xkn ’s are the zeros of the n th power orthogonal polynomial with respect to the weight w and λ0kn ’s are the corresponding Cotes numbers.Furthermore,some results of the convergence for Gaussian quadrature formulas involving the above condition are given.     

Planar graphs without 5-cycles or without 6-cycles

Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8.     

Tension polynomials of graphs

The tension polynomial F_G(k) of a graph G, evaluating the number of nowhere‐zero ?_k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χ_G(k) of G, in that χ_G(k) = k^c(G)F_G(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I_G(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2^r(G)F_G(k)≥I_G(k)≥ (r(G)+1)F_G(k), where r(G)=|V(G)|?c(G), and, for every k>1, F_G(k+1)≥ F_G(k)˙k / (k?1) and I_G(k+1)≥I_G(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002     

On super edge-magic decomposable graphs

Let G be any graph and let {H _i } _i??I be a family of graphs such that $E\left( {H_i } \right) \cap E\left( {H_j } \right) = \not 0$ when i ?? j, ?? _i??I E(H _i ) = E(G) and $E\left( {H_i } \right) \ne \not 0$ for all i ?? I. In this paper we introduce the concept of {H _i } _i??I -super edge-magic decomposable graphs and {H _i } _i??I -super edge-magic labelings. We say that G is {H _i } _i??I -super edge-magic decomposable if there is a bijection ??: V(G) ?? {1,2,..., |V(G)|} such that for each i ?? I the subgraph H _i meets the following two requirements: ??(V(H _i )) = {1,2,..., |V(H _i )|} and {??(a) +??(b): ab ?? E(H _i )} is a set of consecutive integers. Such function ?? is called an {H _i } _i??I -super edge-magic labeling of G. We characterize the set of cycles C _n which are {H ₁, H ₂}-super edge-magic decomposable when both, H ₁ and H ₂ are isomorphic to (n/2)K ₂. New lines of research are also suggested.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Total colorings of planar graphs without adjacent triangles

Let G be a planar graph without adjacent 3-cycles, that is, two cycles of length 3 are not incident with a common edge. In this paper, it is proved that the total coloring conjecture is true for G; moreover, if Δ(G)≥9, then the total chromatic number χ^″(G) of G is Δ(G)+1. Some other related results are obtained, too.     

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

Ideal convergence of continuous functions

For a given ideal I⊆P(ω), IC(I) denotes the class of separable metric spaces X such that whenever is a sequence of continuous functions convergent to zero with respect to the ideal I then there exists a set of integers {m₀<m₁<?} from the dual filter F(I) such that limi→∞fmi(x)=0 for all x∈X. We prove that for the most interesting ideals I, IC(I) contains only singular spaces. For example, if I=Id is the asymptotic density zero ideal, all IC(Id) spaces are perfectly meager while if I=Ib is the bounded ideal then IC(Ib) spaces are σ-sets.     

Bordeaux 3-color conjecture and 3-choosability

A graph G=(V,E) is list L-colorable if for a given list assignment L={L(v):v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27].     

The Linear Arboricity of Planar Graphs without 5-, 6-Cycles with Chords

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that for a planar graph G, ${la(G)=\lceil\frac{\Delta(G)}{2}\rceil}$ if Δ(G) ≥ 7 and G has no 5-cycles with chords, or Δ(G) ≥ 5 and G has no 5-, 6-cycles with chords.     

The Cyclomatic Number of a Graph and its Independence Polynomial at −1

If by s _k is denoted the number of independent sets of cardinality k in a graph G, then ${I(G;x)=s_{0}+s_{1}x+\cdots+s_{\alpha}x^{\alpha}}$ is the independence polynomial of G (Gutman and Harary in Utilitas Mathematica 24:97–106, 1983), where α = α(G) is the size of a maximum independent set. The inequality |I (G; ?1)| ≤ 2 ^ν(G), where ν(G) is the cyclomatic number of G, is due to (Engström in Eur. J. Comb. 30:429–438, 2009) and (Levit and Mandrescu in Discret. Math. 311:1204–1206, 2011). For ν(G) ≤ 1 it means that ${I(G;-1)\in\{-2,-1,0,1,2\}.}$ In this paper we prove that if G is a unicyclic well-covered graph different from C ₃, then ${I(G;-1)\in\{-1,0,1\},}$ while if G is a connected well-covered graph of girth ≥ 6, non-isomorphic to C ₇ or K ₂ (e.g., every well-covered tree ≠ K ₂), then I (G; ?1) = 0. Further, we demonstrate that the bounds {?2 ^ν(G), 2 ^ν(G)} are sharp for I (G; ?1), and investigate other values of I (G; ?1) belonging to the interval [?2 ^ν(G), 2 ^ν(G)].     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A note on 2-nilpotence of finite groups

Ballester-Bolinches and Guo showed that a finite group G is 2-nilpotent if G satisfies: (1) a Sylow 2-subgroup P of G is quaternion-free and (2) Ω₁(P ∩  G′)?≤?Z(P) and N _G (P) is 2-nilpotent. In this paper, it is obtained that G is a non-2-nilpotent group of order 16q for an odd prime q satisfying (1) a Sylow 2-subgroup P of G is not quaternion-free and (2) Ω₁(P?∩?G′)?≤?Z(P) and N _G (P) is 2-nilpotent if and only if q?=?3 and G???GL ₂(3).     

On Parameter Depending Differential Systems Under Carathéodory Conditions

For every λ in a complex domain G, consider on some interval I the initial value problem y′(λ,x) = A(λ,x)y(λ,x) + b(λ,x), y(λ,x₀) - y₀. If this problem satisfies the Carathéodory conditions for every A, then there exist locally absolutely continuous and almost everywhere differentiable solutions y(λ,· ) of the initial value problem. In general, the union N of the exceptional sets N _λ ? I where y(λ, ·) is not differentiate or does not fulfill the differential equation, is not of Lebesgue measure zero. It will be shown that N is of Lebesgue measure zero provided that A and b are holomorphic with respect to λ and their integrals with respect to x are locally bounded on G × I.     

Edge-choosability of planar graphs without adjacent triangles or without 7-cycles

A graph G is edge-L-colorable, if for a given edge assignment L={L(e):e∈E(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.