Planar graph bipartization in linear time

For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k.     

A contribution to queens graphs: A substitution method

A graph G is a queens graph if the vertices of G can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position.We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem.We also prove constructively that any finite subgraph of the rectangular grid or the hexagonal grid is a queens graph.Using a small computer search we solve another conjecture of the authors mentioned above, saying that K_3,4 minus an edge is a minimal non-queens graph.     

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.     

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).     

Some remarks on the odd hadwiger’s conjecture

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K _k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K _k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.     

Parameterized complexity of even/odd subgraph problems

We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Π-graph for Π-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems.For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.     

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.     

Approximate min–max relations for odd cycles in planar graphs

We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio is at most 10. For the corresponding edge version of this problem, Král and Voss recently proved that this ratio is at most 2; we also give a short proof of their result. This work was supported by FNRS, NSERC (PGS Master award, Canada Research Chair in Graph Theory, award 288334-04) and FQRNT (award 2005-NC-98649).     

Note on robust critical graphs with large odd girth

A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn² edges.     

A complete solution to the existence problem for 1‐rotational k‐cycle systems of Kv

The necessary and sufficient conditions for the existence of a 1‐rotational k‐cycle system of the complete graph K_v are established. The proof provides an algorithm able to determine, directly and explicitly, an odd k‐cycle system of K_v whenever such a system exists. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 283–293, 2009     

Half-integral packing of odd cycles through prescribed vertices

The well-known theorem of Erd?s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erd?s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erd?s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erd?s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle.     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

图P^3n的奇优美标号算法

本文讨论了图P^3n的奇优美性,给出了图只奇优美标号算法．     

The chromatic Ramsey number of odd wheels

We prove that the chromatic Ramsey number of every odd wheel W_{2k+ 1}, k?2 is 14. That is, for every odd wheel W_{2k+ 1}, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W_{2k+ 1} in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012     

Colourings of graphs with two consecutive odd cycle lengths

In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K_2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable.     

On domination and reinforcement numbers in trees

The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k. We present an O(k²n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using γ(G)-k dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems.     

Perfect matchings after vertex deletions

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the m×m lattice graph (or grid graph) for m even. Matchings in such grid graphs correspond to coverings of an m×m checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be apart, the resulting graph has a perfect matching. The second class of graphs we consider is a k-fold product graph consisting of k copies of a given graph G with the ith copy joined to the i+1st copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the kth copy of G and find a perfect matching in the product graph with k suitably large.     

Queue layouts of iterated line directed graphs

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph L^k(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^k(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.