Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

Quantum annealing of the graph coloring problem

Quantum annealing extends simulated annealing by introducing artificial quantum fluctuations. The path-integral Monte Carlo version chosen is population-based and designed to be implemented on a classical computer. Its first application to the graph coloring problem is presented in this paper. It is shown by experiments that quantum annealing can outperform classical thermal simulated annealing for this particular problem. Moreover, quantum annealing proved competitive when compared with the best algorithms on most of the difficult instances from the DIMACS benchmarks. The quantum annealing algorithm has even found that the well-known benchmark graph dsjc1000.9 has a chromatic number of at most 222. This is an improvement on its best upper-bound from a large body of literature.     

Adsorption CO2 on the perfect and oxygen vacancy defect surfaces of anatase TiO2 and its photocatalytic mechanism of conversion to CO

The adsorption energies for physisorption and the most stable chemisorption of CO₂ on the neutral charge of perfect anatase [TiO₂] (0 0 1) are −9.03 and −24.66 kcal/mol on the spin-unpolarized and −12.98 and −26.19 kcal/mol on the spin-polarized surface. The small activation barriers of 1.67 kcal/mol on the spin-unpolarized surface and of 6.66 kcal/mol on the spin-unpolarized surface were obtained. The adsorption mechanism of CO₂ on the oxygen vacancy defect [TiO₂ + V_O] surface of anatase TiO₂ using density functional theory calculations was investigated. The energetically preferred conversion of CO₂ to CO was found either on the spin-unpolarized or spin-polarized surfaces of oxygen vacancy defect surface [TiO₂ + V_O] as photocatalyst.     

Coloring graphs from random lists of fixed size

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as ) of the existence of a proper coloring ? of G, such that for every vertex v of G. We show, for all fixed k and growing n, that if , then the probability that G has such a proper coloring tends to 1 as . A similar result for complete graphs is also obtained: if and L is a random ‐list assignment for the complete graph K_n on n vertices, then the probability that K_n has a proper coloring with colors from the random lists tends to 1 as .Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

The distance coloring of graphs

Let G be a connected graph with maximum degree Δ≥ 3.We investigate the upper bound for the chromatic number χγ(G) of the power graph Gγ.It was proved that χγ(G) ≤Δ(Δ-1)γ-1Δ-2+ 1 =:M + 1,where the equality holds if and only if G is a Moore graph.If G is not a Moore graph,and G satisfies one of the following conditions:(1) G is non-regular,(2) the girth g(G) ≤ 2γ- 1,(3)g(G) ≥ 2γ + 2,and the connectivity κ(G) ≥ 3 if γ≥ 3,κ(G) ≥ 4 but g(G) 6 if γ = 2,(4) Δis sufficiently larger than a given number only depending on γ,then χγ(G) ≤ M- 1.By means of the spectral radius λ1(G) of the adjacency matrix of G,it was shown that χ2(G) ≤λ1(G)2+ 1,where the equality holds if and only if G is a star or a Moore graph with diameter 2 and girth 5,and χγ(G)λ1(G)γ+1 ifγ≥3.     

Vertex-distinguishing IE-total Colorings of Cycles and Wheels

Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u）=C（v） for any two different vertices u and v of V （G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt（G）, and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.     

Sub-exponential graph coloring algorithm for stencil-based Jacobian computations

Partial differential equations can be discretized using a regular Cartesian grid and a stencil-based method to approximate the partial derivatives. The computational effort for determining the associated Jacobian matrix can be reduced. This reduction can be modeled as a (grid) coloring problem. Currently, this problem is solved by using a heuristic approach for general graphs or by developing a formula for every single stencil. We introduce a sub-exponential algorithm using the Lipton–Tarjan separator in a divide-and-conquer approach to compute an optimal coloring. The practical relevance of the algorithm is evaluated when compared with an exponential algorithm and a greedy heuristic.     

若干冠图的邻点可区别V-全染色

应用构造染色函数法研究了冠图C_m·C_n、C_m·C_n的邻点可区别V-全染色.通过对P_m·C_n的邻点可区别V-全染色的研究巧妙给出了C_m·C_n邻点可区别V-全染色,并得到了这些图的邻点可区别V-全色数,从而验证了图的邻点可区别V-全染色猜想.     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is 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 coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.