Approximating the maximum 3-edge-colorable subgraph problem

We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where γ_o(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 as k goes to infinity are also known. At present, the best known performance ratios for the cases k=2 and k=3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C₅’s are also banned).     

Factors and vertex-deleted subgraphs

A relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271-277] proved that for even integer k, if G-x has a k-factor for each x∈V(G), then G has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, Discrete Math. 220 (2000) 239-242] generalized Katerinis’ result to f-factors, and proved that if G-x has an f-factor for each x∈V(G), then G has an f-factor for an integer-valued function f defined on V(G) with even. In this paper, we consider a similar problem to that of Enomoto and Tokuda, where for several vertices x we do not have to know whether G-x has an f-factor. Let G be a graph, X be a set of vertices, and let f be an integer-valued function defined on V(G) with even, |V(G)-X|?2. We prove that if and if G-x has an f-factor for each x∈V(G)-X, then G has an f-factor. Moreover, if G excludes an isolated vertex, then we can replace the condition with . Furthermore the condition will be when |X|=1.     

Nowhere-zero 3-flow of graphs with small independence number

Tutte’s $3$-flow conjecture states that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we characterize all graphs with independence number at most $4$ that admit a nowhere-zero $3$-flow. The characterization of $3$-flow verifies Tutte’s $3$-flow conjecture for graphs with independence number at most $4$ and with order at least $21$. In addition, we prove that every odd-$5$-edge-connected graph with independence number at most $3$ admits a nowhere-zero $3$-flow. To obtain these results, we introduce a new reduction method to handle odd wheels.     

Coding of geodesics on some modular surfaces and applications to odd and even continued fractions

The connection between geodesics on the modular surface $PSL(2,\mathbb{Z})?\mathbb{H}$ and regular continued fractions, established by Series, is extended to a connection between geodesics on $\Gamma ?\mathbb{H}$ and odd and grotesque continued fractions, where $\Gamma ?{\mathbb{Z}}_{3}1{\mathbb{Z}}_3$ is the index two subgroup of $PSL(2,\mathbb{Z})$ generated by the order three elements $\left(\begin{array}{cc}\hfill 0\hfill & \hfill ?1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right)$ and $\left(\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill ?1\hfill & \hfill 1\hfill \end{array}\right)$, and having an ideal quadrilateral as fundamental domain.A similar connection between geodesics on $\Theta ?\mathbb{H}$ and even continued fractions is discussed in our framework, where $\Theta$ denotes the Theta subgroup of $PSL(2,\mathbb{Z})$ generated by $\left(\begin{array}{cc}\hfill 0\hfill & \hfill ?1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \end{array}\right)$ and $\left(\begin{array}{cc}\hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$.     

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010     

A parallel algorithm for solving Toeplitz linear systems

Numerical methods of solution are considered for systems which are Toeplitz and symmetric. In our case, the coefficient matrix is essentially tridiagonal and sparse. There are two distinct approaches to be considered each of which is efficient in its own way. Here we will combine the two approaches which will allow application of the cyclic reduction method to coefficient matrices of more general forms. The convergence of the approximations to the exact solution will also be examined. Solving linear systems by the adapted cyclic reduction method can be parallel processed.     

直径为3的3-正则简单平面图的完全刻画

通过对子图和围长的研究,完全刻画了直径为3的3-正则简单平面图,获得了这类图仅有的11个非同构图.     

Convex Envelopes of Monomials of Odd Degree

Convex envelopes of nonconvex functions are widely used to calculate lower bounds to solutions of nonlinear programming problems (NLP), particularly within the context of spatial Branch-and-Bound methods for global optimization. This paper proposes a nonlinear continuous and differentiable convex envelope for monomial terms of odd degree, x ^2k+1, where k N and the range of x includes zero. We prove that this envelope is the tightest possible. We also derive a linear relaxation from the proposed envelope, and compare both the nonlinear and linear formulations with relaxations obtained using other approaches.