The Erd?s-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces

We prove that for any orientable surface S and any non-negative integer k, there exists an integer f_S(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most f_S(k) such that G-A is bipartite. Such a property is called the Erd?s-Pósa property for odd cycles. We also show its edge version. As Reed [Mangoes and blueberries, Combinatorica 19 (1999) 267-296] pointed out, the Erd?s-Pósa property for odd cycles do not hold for all non-orientable surfaces.     

Chromatic numbers of quadrangulations on closed surfaces

It has been shown that every quadrangulation on any nonspherical orientable closed surface with a sufficiently large representativity has chromatic number at most 3. In this paper, we show that a quadrangulation G on a nonorientable closed surface N_k has chromatic number at least 4 if G has a cycle of odd length which cuts open N_k into an orientable surface. Moreover, we characterize the quadrangulations on the torus and the Klein bottle with chromatic number exactly 3. By our characterization, we prove that every quadrangulation on the torus with representativity at least 9 has chromatic number at most 3, and that a quadrangulation on the Klein bottle with representativity at least 7 has chromatic number at most 3 if a cycle cutting open the Klein bottle into an annulus has even length. As an application of our theory, we prove that every nonorientable closed surface N_k admits an eulerian triangulation with chromatic number at least 5 which has arbitrarily large representativity. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 100–114, 2001     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

A counterexample to the odd 2–factored snarks conjecture

A snark is a cubic cyclically 4–edge connected graph with edge chromatic number four and girth at least five. We say that a graph G is odd 2–factored if for each 2–factor F of G each cycle of F is odd. In this extended abstract, we present a method for constructing odd 2–factored snarks. In particular, we construct two families of odd 2–factored snarks of order 26 and 34 that disprove a previous conjecture by some of the authors.     

Decompositions for edge-coloring join graphs and cobipartite graphs

An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph G is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G). To determine whether a graph G is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720]. First, we propose edge-decompositions of a graph G with the goal of edge-coloring G with Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135-147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.     

Degenerate and star colorings of graphs on surfaces

We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of Fertin et al. (2004) [8]: If G is a graph of maximum degree Δ, then G admits a degenerate star coloring using O(Δ^3/2) colors. We use this result to prove that every graph of genus g admits a degenerate star coloring with O(g^3/5) colors. It is also shown that these results are sharp up to a logarithmic factor.     

Coloring the cliques of line graphs

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals $2$ is NP-complete. We deal with the CCHN of the graph itself as well.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs. We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K_{⌈t/2⌉,⌊t/2⌋} in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases. As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. * Research partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321. † Research partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.     

Coloring vertices and faces of maps on surfaces

The vertex-face chromatic number of a map on a surface is the minimum integer m such that the vertices and faces of the map can be colored by m colors in such a way that adjacent or incident elements receive distinct colors. The vertex-face chromatic number of a surface is the maximal vertex-chromatic number for all maps on the surface. We give an upper bound on the vertex-face chromatic number of the surfaces of Euler genus ≥2. The upper bound is less (by 1) than Ringel’s upper bound on the 1-chromatic number of a surface for about 5/12 of all surfaces. We show that there are good grounds to suppose that the upper bound on the vertex-face chromatic number is tight.     

Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces

For a graph property P and a graph G, we define the domination subdivision number with respect to the property P to be the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to change the domination number with respect to the property P. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces.     

Chromatic Polynomials of Complements of Bipartite Graphs

We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root.     

On the chromatic index of outerplanar graphs

Vizing [Diskret. Analiz3 (1964), 25–30] has shown that if ? denotes the maximum valency of a simple graph, then its chromatic index is either ? or ? + 1. The object of this paper is to show that the chromatic index of an outerplanar graph G is ? if and only if G is not an odd circuit.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Improved upper bounds on acyclic edge colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors.The acyclic chromatic index of a graph G,denoted by a′(G),is the minimum number k such that there is an acyclic edge coloring using k colors.It is known that a′(G)≤16△for every graph G where △denotes the maximum degree of G.We prove that a′(G)13.8△for an arbitrary graph G.We also reduce the upper bounds of a′(G)to 9.8△and 9△with girth 5 and 7,respectively.     

Spanning quadrangulations of triangulated surfaces

In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph \(G^*\) is nonbipartite, then \(G^*\) has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph \(G^*\) is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation.