Planar graphs decomposable into a forest and a matching

He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.     

Approximating maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n³m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was .     

A note on flow polynomials of graphs

Using the decomposition theory of modular and integral flow polynomials, we answer a problem of Beck and Zaslavsky, by providing a general situation in which the integral flow polynomial is a multiple of the modular flow polynomial.     

On the unimodality of independence polynomials of very well-covered graphs

The independence polynomial $i(G,x)$ of a graph $G$ is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $n∕2$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.     

A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G_n,p with the minimal number of colors and has expected linear running time, provided that np≤1.33.     

The hierarchical product of graphs

A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree T_m (which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

A survey on labeling graphs with a condition at distance two

For positive integers k,d₁,d₂, a k-L(d₁,d₂)-labeling of a graph G is a function f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|?d_i whenever the distance between u and v is i in G, for i=1,2. The L(d₁,d₂)-number of G, λ_d1,d2(G), is the smallest k such that there exists a k-L(d₁,d₂)-labeling of G. This class of labelings is motivated by the code (or frequency) assignment problem in computer network. This article surveys the results on this labeling problem.     

The homology of the cyclic coloring complex of simple graphs

Let G be a simple graph on n vertices, and let χG(λ) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Δ(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n−3)rd homology group of Δ(G) is equal to (n−(r+1)) plus , where is the rth derivative of χG(λ). We also define a complex ΔC(G), whose r-faces consist of all ordered set partitions [B₁,…,Br+2] where none of the Bi contain an edge of G and where 1∈B₁. We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x₁,…,xn]/{xixj|ij is an edge of G}. We show that when G is a connected graph, the homology of ΔC(G) has nonzero homology only in dimension n−2, and the dimension of this homology group is . In this case, we provide a bijection between a set of homology representatives of ΔC(G) and the acyclic orientations of G with a unique source at v, a vertex of G.     

Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

The chromatic polynomial P_G(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (−∞,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

A note on the DP-chromatic number of complete bipartite graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvo?ák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{?}\left(G\right)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}\left(G\right)$. On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{?}\left(K_{k,t}\right)=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}\left(K_{k,t}\right)=k+1$ if $t\ge 1+(k^k∕k!)(log(k!)+1)$, and we show that ${\chi }_{DP}\left(K_{k,t}\right)<k+1$ if $t<k^k∕k!$.     

Multivariate matching polynomials of cyclically labelled graphs

We consider the matching polynomials of graphs whose edges have been cyclically labelled with the ordered set of t labels {x₁,…,x_t}.We first work with the cyclically labelled path, with first edge label x_i, followed by N full cycles of labels {x₁,…,x_t}, and last edge label x_j. Let Φ_i,Nt+j denote the matching polynomial of this path. It satisfies the (τ,Δ)-recurrence: , where τ is the sum of all non-consecutive cyclic monomials in the variables {x₁,…,x_t} and . A combinatorial/algebraic proof and a matrix proof of this fact are given. Let G_N denote the first fundamental solution to the (τ,Δ)-recurrence. We express G_N (i) as a cyclic binomial using the symmetric representation of a matrix, (ii) in terms of Chebyshev polynomials of the second kind in the variables τ and Δ, and (iii) as a quotient of two matching polynomials. We extend our results from paths to cycles and rooted trees.     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).