Total chromatic number of graphs with small genus

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with k colors. Denote χ_ve (G) the total chromatic number of G, and c(Σ) the Euler characteristic of a surfase Σ. In this paper, we prove that for any simple graph G which can be embedded in a surface Σ with Euler characteristic c(Σ), χ_ve (G) = Δ (G) + 1 if c(Σ) > 0 and Δ (G) ≥ 13, or, if c(Σ) = 0 and Δ (G) ≥ 14. This result generalizes results in [3], [4], [5] by Borodin.     

Constructions of Large Graphs on Surfaces

We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k, determine the maximum order N(Δ,k,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs. Given a surface Σ of Euler genus g and an odd diameter k, the current best asymptotic lower bound for N(Δ,k,Σ) is given by $$\sqrt{\frac{3}{8}}g \Delta^{\lfloor k/2 \rfloor}.$$ Our constructions produce new graphs of order $$\left\{\begin{array}{ll}6 \Delta^{\lfloor k/2 \rfloor} \qquad \qquad \qquad \qquad {\rm if \Sigma\;is\;the\;Klein\;bottle} \\ \left(\frac{7}{2} + \sqrt{6g + \frac{1}{4}}\right) \Delta^{\lfloor k/2 \rfloor} \quad {\rm otherwise},\end{array}\right.$$ thus improving the former value.     

Edge coloring of graphs with small maximum degrees

By applying a discharging method, we give new lower bounds for the sizes of edge chromatic critical graphs for small maximum degrees. Furthermore, it is also proved that if G is a graph embeddable in a surface S with characteristic c_S=−4 or −5 or −6, then G is class one if its maximum degree Δ≥10 or 11 or 12 respectively.     

Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5

For each surface Σ, we define Δ(Σ) = max{Δ(G)|Gis a class two graph of maximum degree Δ(G) that can be embedded in Σ}. Hence, Vizing's Planar Graph Conjecture can be restated as Δ(Σ) = 5 if Σ is a plane. In this paper, we show that Δ(Σ) = 9 if Σ is a surface of characteristic χ(Σ) = ?5. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:148‐168, 2011     

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations.We show that a graph has NLCT-width 1 if and only if it is (C₄,P₄)-free. Since (C₄,P₄)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C₄,P₄,2K₂)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs.We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P₄, 2K₂, and co-2P₃.     

Cliques in $$C_4$$-free graphs of large minimum degree

A graph G is called \(C_4\)-free if it does not contain the cycle \(C_4\) as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erd?s) a peculiar property of \(C_4\)-free graphs: \(C_4\)-free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least \(c'n\) (with \(c'= 0.1c^2\)). We prove here better bounds \(\big ({c^2n\over 2+c}\) in general and \((c-1/3)n\) when \( c \le 0.733\big )\) from the stronger assumption that the \(C_4\)-free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular \(C_4\)-free graphs on \(4k+1\) vertices contain a clique of size \(k+1\). This is the best possible as shown by the kth power of the cycle \(C_{4k+1}\).     

Neighbor Sum Distinguishing Index

We consider proper edge colorings of a graph G using colors of the set {1, . . . , k}. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by ndi_Σ(G). In the paper we conjecture that for any connected graph G ≠ C ₅ of order n ≥ 3 we have ndi_Σ(G) ≤ Δ(G) + 2. We prove this conjecture for several classes of graphs. We also show that ndi_Σ(G) ≤ 7Δ(G)/2 for any graph G with Δ(G) ≥ 2 and ndi_Σ(G) ≤ 8 if G is cubic.     

Real closures of models of weak arithmetic

D’Aquino et al. (J Symb Log 75(1):1–11, 2010) have recently shown that every real-closed field with an integer part satisfying the arithmetic theory IΣ₄ is recursively saturated, and that this theorem fails if IΣ₄ is replaced by IΔ₀. We prove that the theorem holds if IΣ₄ is replaced by weak subtheories of Buss’ bounded arithmetic: PV or ${\Sigma^b_1-IND^{|x|_k}}$ . It also holds for IΔ₀ (and even its subtheory IE ₂) under a rather mild assumption on cofinality. On the other hand, it fails for the extension of IOpen by an axiom expressing the Bézout property, even under the same assumption on cofinality.     

On minimally 3-connected graphs on a surface

It is well known that the maximal size of minimally 3-connected graphs of order n ≥ 7 is 3n-9. In this paper, we shall prove that if G is a minimally 3-connected graph of order n, and is embedded in a closed surface with Euler characteristic χ, then G contains at most 2n- min {2, 2χ} edges. This bound is best possible for every closed surface.     

On a conjecture of Erdős and Simonovits: Even cycles

Let F be a family of graphs. A graph is F-free if it contains no copy of a graph in F as a subgraph. A cornerstone of extremal graph theory is the study of the Turán number ex(n,F), the maximum number of edges in an F-free graph on n vertices. Define the Zarankiewicz number z(n,F) to be the maximum number of edges in an F-free bipartite graph on n vertices. Let C _k denote a cycle of length k, and let C _k denote the set of cycles C _?, where 3≤?≤k and ? and k have the same parity. Erd?s and Simonovits conjectured that for any family F consisting of bipartite graphs there exists an odd integer k such that ex(n,F ∪ C _k ) ～ z(n,F) — here we write f(n) ～ g(n) for functions f,g: ? → ? if lim _n→∞ f(n)/g(n)=1. They proved this when F ={C ₄} by showing that ex(n,{C ₄;C ₅})～z(n,C ₄). In this paper, we extend this result by showing that if ?∈{2,3,5} and k>2? is odd, then ex(n,C _2? ∪{C _k }) ～ z(n,C _2? ). Furthermore, if k>2?+2 is odd, then for infinitely many n we show that the extremal C _2? ∪{C _k }-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd k<2?, and furthermore the asymptotic result does not hold when (?,k) is (3, 3), (5, 3) or (5, 5). Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Packing and Covering Triangles in K 4-free Planar Graphs

We show that every K ₄-free planar graph with at most ν edge-disjoint triangles contains a set of at most ${\frac32\nu}$ edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c?<?2 there are K ₄-free graphs with at most ν edge-disjoint triangles that need more than cν edges to cover all triangles.     

Stable closed characteristics on partially symmetric convex hypersurfaces

Let n be a positive integer and P=diag(−I_n−κ,I_κ,−I_n−κ,I_κ) for some integer κ∈[0,n]. In this paper, we prove that for any convex compact smooth hypersurface Σ in R²ⁿ with n?2 there always exists at least one closed characteristic on Σ which possesses at least 2n−4κ Floquet multipliers on the unit circle of the complex plane, provided Σ is P-symmetric, i.e., x∈Σ implies Px∈Σ.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Geometric rigidity for analytic estimates of Müller–?verák

In the paper Müller–?verák (J Differ Geom 42(2):229–258, 1995) conformally immersed surfaces with finite total curvature were studied. In particular it was shown that surfaces with total curvature ${\int_{\Sigma} |A|^2 < 8 \pi}$ in dimension three were embedded and conformal to the plane with one end. Here, using techniques from Kuwert–Li (W ^2,2-conformal immersions of a closed Riemann surface into R ⁿ . arXiv:1007.3967v2 [math.DG], 2010), we will show that if the total curvature ${ \int_{\Sigma}|A|^2\leq8\pi}$ , then we are either embedded and conformal to the plane, isometric to a catenoid or isometric to Enneper’s minimal surface. In fact the technique of our proof shows that if we are conformal to the plane, then if n?≥ 3 and ${ \int_{\Sigma} | A|^{2}\leq 16 \pi }$ then Σ is embedded or Σ is the image of a generalized catenoid inverted at a point on the catenoid. In order to prove these theorems, we prove a Gauss–Bonnet theorem for surfaces with complete ends and isolated finite area singularities which extends a theorem of Jorge-Meeks (Topology 22(2):203–221, 1983). Using this theorem, we then prove an inversion formula for the Willmore energy.     

On acyclic colorings of graphs on surfaces

A properk-coloring of a graph is acyclic if every 2-chromatic subgraph is acyclic. Borodin showed that every planar graph has an acyclic 5-coloring. This paper shows that the acyclic chromatic number of the projective plane is at most 7. The acyclic chromatic number of an arbitrary surface with Euler characteristic η=−γ is at mostO(γ^4/7). This is nearly tight; for every γ>0 there are graphs embeddable on surfaces of Euler characteristic −γ whose acyclic chromatic number is at least Ω(γ^4/7/(logγ)^1/7). Therefore, the conjecture of Borodin that the acyclic chromatic number of any surface but the plane is the same as its chromatic number is false for all surfaces with large γ (and may very well be false for all surfaces). This author's research was supported in part by a United States Israeli BSF grant. This author's research was supported by the Ministry of Research and Technology of Slovenia, Research Project P1-0210-101-92. This author's research was supported by the Office of Naval Research, grant number N00014-92-J-1965.     

Forbidden induced subgraphs for star-free graphs

Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K_1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.     

Do 3n − 5 edges force a subdivision of K5?

A conjecture of Dirac states that every simple graph with n vertices and 3n ? 5 edges must contain a subdivision of K₅. We prove that a topologically minimal counterexample is 5-connected, and that no minor-minimal counterexample contains K₄ – e. Consequently, Dirac's conjecture holds for all graphs that can be embedded in a surface with Euler characteristic at least ? 2.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

2K2 vertex-set partition into nonempty parts

A graph is 2K₂-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K₂-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C₄-free graphs, circular-arc graphs, spiders, P₄-sparse graphs, and bipartite graphs the 2K₂-partition problem can be solved in polynomial time.