Search

The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose components are paths of length at most 2. In this paper, we prove that every planar graph G with =10 has la2(G)9. Using this result, we correct an error in the proof of a result in Wang (2016), which says that every planar graph G satisfies la2(G)(+1)2+6.

A book embedding of a graph G is an embedding of vertices of G along the spine of a book, and edges of G on the pages so that no two edges on the same page intersect. Malitz (1994) proved that any graph on the orientable surface S g of genus g has a book embedding with O ( g ) pages. In this paper, we prove that every locally planar graph on S g (i.e., one with high representativity) has a book embedding with seven pages.

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. The anti-Ramsey number a r ( G , H ) is the maximum number of colors in an edge-coloring of G with no rainbow copy of H . Anti-Ramsey numbers were introduced by Erd?s et?al. (1973) and studied in numerous papers. Originally a complete graph was considered as G , but afterwards also other graphs were used as host graphs.We consider a complete split graph as the host graph and discuss some results for the graph H containing short cycles or triangles with pendant edges. Among others we show that a r ( K n + K s ? , C 3 + ) = a r ( K n + K s ? , C 3 ) = n + s - 1 for n , s ? 1 , where C 3 + denotes a triangle with a pendant edge.

In this paper, we study the odd K m -minor problem in even embeddings on surfaces. We first establish a general theory for even embeddings with odd K m -minors. Given an integer m we show that for every surface F 2 of sufficiently high genus there exists a constant N = N ( F 2 ) so that every non-bipartite even embedding on F 2 with representativity at least N contains an odd K m as a minor. In the second part we prove that every 19-representative non-bipartite even embedding in an arbitrary orientable surface of genus ? 1 has an odd K 5 -minor.

The linear 2-arboricity la 2 ( G ) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that if G is a planar graph, then la 2 ( G ) ? ? ( Δ ( G ) + 1 ) / 2 ? + 6 . This improves a result in Lih et?al. (2003), which says that every planar graph G satisfies la 2 ( G ) ? ? ( Δ ( G ) + 1 ) / 2 ? + 12 .

A graph G is locally planar if it is embedded in a surface with large edge-width. Thomassen (1993) proved that every graph embedded in a fixed surface with sufficiently large edge-width is 5-colourable. DeVos et?al. (2008) strengthened this result and proved that every graph embedded in a fixed surface with sufficiently large edge-width is 5-choosable. This paper further strengthens the result to on-line list colouring and proves that every graph embedded in a fixed surface with sufficiently large edge-width is 5-paintable.

This paper discusses the game coloring number of planar graphs. Let G be a planar graph and let col g ( G ) be the game coloring number of G . We prove that col g ( G ) is at most 13 if G is a planar graph with girth at least 4. We also show that there is a planar graph G with girth 4 such that col g ( G ) ≥ 7 and there is a planar graph with girth 5 such that col g ( G ) ≥ 6 .

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph K m , n into paths P k + 1 and stars S k + 1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3 k , and we give a complete solution when k = 3 . We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4 k , there exists a decomposition of the complete graph K n into p copies of P k + 1 and q copies of S k + 1 if and only if k ( p + q ) = n 2 .

Let H be a simple graph. A graph G is called an H -saturated graph if H is not a subgraph of G , but adding any missing edge to G will produce a copy of H . Denote by S A T ( n , H ) the set of all H -saturated graphs G with order n . Then the saturation number s a t ( n , H ) is defined as min G ∈ S A T ( n , H ) | E ( G ) | , and the extremal number e x ( n , H ) is defined as max G ∈ S A T ( n , H ) | E ( G ) | . A natural question is that of whether we can find an H -saturated graph with m edges for any s a t ( n , H ) ≤ m ≤ e x ( n , H ) . The set of all possible values m is called the edge spectrum for H -saturated graphs. In this paper we investigate the edge spectrum for P i -saturated graphs, where 2 ≤ i ≤ 6 . It is trivial for the case of P 2 that the saturated graph must be an empty graph.

A graph is k-supereulerian if it has a spanning even subgraph with at most k components. We show that if G is a connected graph and G′ is the (collapsible) reduction of G, then G is k-supereulerian if and only if G′ is k-supereulerian. This extends Catlin’s reduction theorem in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. For a graph G, let F(G) be the minimum number of edges whose addition to G create a spanning supergraph containing two edge-disjoint spanning trees. We prove that if G is a connected graph with F(G)≤k, where k is a positive integer, then either G is k-supereulerian or G can be contracted to a tree of order k+1. This is a best possible result which extends another theorem of Catlin, in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. Finally, we use these results to give a sufficient condition on the minimum degree for a graph G to bek-supereulerian.

The length of a longest cycle in a graph G is called the circumference of G and is denoted by c(G). Let c(n)=min{c(G):G is a 3-connected cubic planar graph of order n}. Tait conjectured in 1884 that c(n)=n, and Tutte disproved this in 1946 by showing that c(n)≤n−1 for n=46. We prove that the inequality c(n)≤n−n+494+52 holds for infinitely many integers n. The exact value of c(n) is unknown.

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.

We show that, for any given non-spherical orientable closed surface F2, there exists an optimal 1-planar graph which can be embedded on F2 as a triangulation. On the other hand, we prove that there does not exist any such graph for the nonorientable closed surfaces of genus at most 3.

A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors. Grötzsch’s theorem [4] states that every planar triangle-free graph is 3-colorable. However, Voigt [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325–328] gave an example of such a graph that is not 3-choosable, thus Grötzsch’s theorem does not generalize naturally to choosability. We prove that every planar triangle-free graph without 7- and 8-cycles is 3-choosable.

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K2 and K4 is 2 and to prove that a minimal 2-matching-covered graph other than K4 cannot contain a complete subgraph with at least 4 vertices.

Let H be a fixed graph. A graph G has an H-decomposition if the edge set of G can be partitioned into subsets inducing graphs isomorphic to H. Let PH denote the following decision problem: “Does an instance graph G admit H-decomposition?” In this paper we prove that the problem PH is polynomial time solvable if H is a graph whose every component has at most 2 edges. This way we complete a solution of Holyer’s problem which is the problem of classifying the problems PH according to their computational complexities.

Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let (P"1"0)"@m"@? be the graph obtained from the Petersen graph by contracting @m edges from a perfect matching. In this paper we prove that every bridgeless (P"1"0)"3"@?-minor free graph admits a nowhere-zero 4-flow.

The instance of the problem of finding 2-factors in an orientated graph with forbidden transitions consists of an orientated graph G and for each vertex v of G, a graph H"v of allowed transitions at v. Vertices of the graph H"v are the edges incident to v. An orientated 2-factor F of G is called legal if all the transitions are allowed, i.e. for every vertex v, the two edges of F adjacent to it form an edge in H"v. Deciding whether a legal 2-factor exists in G is NP-complete in general. We investigate the case when the graphs of allowed transitions are taken from some fixed class C. We provide an exact characterization of classes C so that the problem is NP-complete. In particular, we prove a dichotomy for this problem, i.e. that for any class C it is either polynomial or NP-complete.

The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most ${\it \Delta}+2$, where ${\it \Delta}$ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, in 2005 Maydanskiy proved that the conjecture holds for any graph with ${\it \Delta}\leq 3$. It is easily deduced that the incidence coloring number of a semi-cubic graph is 4 or 5. In this paper, we show that it is already NP-complete to determine if a semi-cubic graph is 4-incidence colorable, and therefore it is NP-complete to determine if a general graph is $k$-incidence colorable., Comment: 11 pages

A well-known conjecture of Scott Smith is that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k≥2. We provide a dual version of this conjecture for two distinct largest bonds in a graph. This dual conjecture is established for k⩽6.

A graph G is said to be F-saturated if G does not contain a copy of F as a subgraph and G+e contains a copy of F as a subgraph for any edge e contained in the complement of G. Erdos et al. in [A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107-1110.] determined the minimum number of edges, sat(n,F), such that a graph G on n vertices must have when F is a t-clique. Later, Ollmann [K"2","2-saturated graphs with a minimal number of edges, in: Proceedings of the Third SouthEast Conference on Combinatorics, Graph Theory and Computing, 1972, pp. 367-392.] determined sat(n,F) for F=K"2","2. Here we give an upper bound for sat(n,F) when F=K"t^2 the complete t-partite graph with partite sets of size 2, and prove equality when G is of prescribed minimum degree.

Let Gw=(V,E,w) be a weighted graph, where G=(V,E) is its underlying graph and w:E→[1,∞) is the edge weight function. A (circular) p-coloring of Gw is a mapping c of its vertices into a circle of perimeter p so that every edge e=uv satisfies dist(c(u),c(v))⩾w(uv). The smallest p allowing a p-coloring of Gw is its circular chromatic number, χc(Gw).A p-basic graph is a weighted complete graph, whose edge weights satisfy triangular inequalities, and whose optimal traveling salesman tour has length p. Weighted Hadwiger's conjecture (WHC) at p⩾1 states that if p is the largest real number so that Gw contains some p-basic graph as a weighted minor, then χc(Gw)⩽p.We prove that WHC is true for p

The Hadwiger number @h(G) of a graph G is the largest integer h such that the complete graph on h nodes K"h is a minor of G. Equivalently, @h(G) is the largest integer such that any graph on at most @h(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, @h(G)>[email protected](G), where @g(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G"[email protected]?G"[email protected][email protected]?G"k, where each G"i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently. In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least 2log"2(@g(G))+3. In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least 2log"2(@g(G))+3, for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then @h(G)>[email protected](G)^@?^(^d^-^1^)^/^2^@?, and thus G satisfies the Hadwiger's conjecture when d>=3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture. Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube H"d, 2^@?^(^d^-^1^)^/^2^@?=

In this paper we continue our investigations from [R. Haggkvist, K. Markstrom, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umea University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].

Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph. In this paper we study minimal triangulations, which are the result of adding an inclusion minimal set of edges to produce a triangulation. This topic was first studied from the standpoint of sparse matrices and vertex elimination in graphs. Today we know that minimal triangulations are closely related to minimal separators of the input graph. Since the first papers presenting minimal triangulation algorithms appeared in 1976, several characterizations of minimal triangulations have been proved, and a variety of algorithms exist for computing minimal triangulations of both general and restricted graph classes. This survey presents and ties together these results in a unified modern notation, keeping an emphasis on the algorithms.

A simple graph is reflexive if its second largest eigenvalue does not exceed 2. A graph is treelike (sometimes also called a cactus) if all its cycles (circuits) are mutually edge-disjoint. In a lot of cases one can establish whether a given graph is reflexive by identifying and removing a single cut-vertex (Theorem 1). In this paper we prove that, if this theorem cannot be applied to a connected treelike reflexive graph G and if all its cycles do not have a common vertex (do not form a bundle), such a graph has at most five cycles (Theorem 2). On the same conditions, in Theorem 3 we find all maximal treelike reflexive graphs with four and five cycles.

A set W⊆V(G) is called homogeneous in a graph G if 2⩽|W|⩽|V(G)|-1, and N(x)⧹W=N(y)⧹W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)⧹{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83–97) is the following sufficient condition.TheoremIf every homogeneous set of G has exactly two vertices then Ext(G) is a finite set.We extend this result to a wider class of graphs. A graph is simple if it is isomorphic to an induced subgraph of the path P4.TheoremIf every homogeneous set of G induces a simple graph then Ext(G) is a finite set.We show that our result is best possible in the following sense. Specifically, we prove that for every non-simple graph F there exist a graph G and a homogeneous set W of G such that W induces a subgraph isomorphic to F and Ext(G) is infinite.

Let G be an undirected and loopless finite graph that is not a path. The smallest integer m such that the iterated line graph Lm(G) is hamiltonian is called the hamiltonian index of G, denoted by h(G). A reduction method to determine the hamiltonian index of a graph G with h(G)⩾2 is given here. We use it to establish a sharp lower bound and a sharp upper bound on h(G), respectively, thereby improving some known results of Catlin et al. [J. Graph Theory 14 (1990) 347] and Hong-Jian Lai [Discrete Math. 69 (1988) 43]. Examples show that h(G) may reach all integers between the lower bound and the upper bound. We also propose some questions on the topic.

Let H be a graph with κ1 components and κ2 blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|⩽α(κ1−1)+β(κ2−1) for all (α,β) such that α+β⩾5,2α+5β⩾20, and β⩾3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.

Given two graphs G and H, an H-matching of G (or a tiling of G with H) is a subgraph of G consisting of vertex-disjoint copies of H. For an r-chromatic graph H on h vertices, we write u=u(H) for the smallest possible color-class size in any r-coloring of H. The critical chromatic number of H is the number χcr(H)=(r−1)h/(h−u). A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n-vertex graph of minimum degree at least (1−(1/χcr(H)))n, then G contains an H-matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n when H is a 3-chromatic graph.

Let G be a simple graph with n vertices and tw(G) be the tree-width of G. Let ρ(G) be the spectral radius of G and λ(G) be the smallest eigenvalue of G. The join G∇H of disjoint graphs of G and H is the graph obtained from G+H by joining each vertex of G to each vertex of H. In this paper, several results which are concerned with tree-width, clique-minors, and eigenvalues of graphs are given. In particular, we have(1) If G is K5 minor-free graph, thenρ(G)⩽1+3n−8,where equality holds if and only if G is isomorphic to K3∇(n−3)K1.(2) If G is K5 minor-free graph with n⩾5 vertices, thenλ(G)⩾−3n−9,where equality holds if and only if G is isomorphic to K3,n−3.

A graph H decomposes a graph G if and only if the edges of G can be partitioned into disjoint subsets each of which induces a graph isomorphic to H. Wilson (in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975) showed, among other things, that for any graph H, there is an integer n such that H decomposes K"n, andHaggkvist (in: J. Siemons (Ed.), Surveys in Combinatories 1989, Invited papers for 12th British Combinatorial Conference, LMS Lecture Notes 141, Cambridge University Press, Cambridge, 1989, pp. 115-147) showed that for any bipartite H, there is an n such that H decomposes K"n","n. In this paper, we extend this result to tripartite graphs, by showing that for any tripartite graph H, there is an integer n such that H decomposes K"n","n","n.

Harary's edge reconstruction conjecture states that a graph G=(V,E) with at least four edges is uniquely determined by the multiset of its edge-deleted subgraphs, i.e. the graphs of the form G−e for e∈E. It is well-known that this multiset uniquely determines the degree sequence of a graph with at least four edges. In this note we generalize this result by showing that the degree sequence of a graph with at least four edges is uniquely determined by the set of the degree sequences of its edge-deleted subgraphs with one well-described class of exceptions. Moreover, the multiset of the degree sequences of the edge-deleted subgraphs always allows one to reconstruct the degree sequence of the graph.

The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases.

In this paper, we study one measure of complexity of a graph, namely its type. The type of a graph G is defined to be the minimum number n such that there is a sequence of graphs G=G0,G1,…,Gn, where Gi is obtained by contracting one edge in or deleting one edge from each block of Gi−1, and where Gn is edgeless. We show that a 3-connected graph has large type if and only if it has a minor isomorphic to a large fan. Furthermore, we show that if a graph has large type, then it has a minor isomorphic to a large fan or to a large member of one of two specified families of graphs.

Let G be a graph embedded in the sphere. A k-nest of a point x not in G is a collection C1,…,Ck of disjoint cycles such that for each Ci, the side containing x also contains Cj for each j

For a graph G let RM( G ) be the smallest integer R, if it exists, such that every coloring of the edges of K R by an arbitrary number of colors implies a subgraph of K R isomorphic to G that is either monochromatic or has the property that no two of its edges have the same color. We generalize the theorem r ( nK 2 , n −1)= n 2 − n +2, where r ( nK 2 , n −1) is the Ramsey number for n matchings in an ( n −1)-coloring of the complete graph. Namely, we prove that RM( nK 2 )= r ( nK 2 , n −1)= n 2 − n +2. In addition, we generalize the theorem r ( nK 2 ,2)=3 n −1 by considering colorings with three and five colors. Several further possible generalizations for hypermatchings in hypergraphs are suggested.

Piazza, Roberts and Stueckle recently conjectured that every complete n -partite graph is strictly edge-tenacious. In this paper, we establish a necessary and sufficient condition for a graph to be edge-tenacious. We apply these results to prove the conjecture of Piazza et al.

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V 8 (the Mobius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V 8 -minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.

We will prove a d-dimensional version of the Geelen and Simpson theorem. c 2000 Elsevier Science B.V. All rights reserved.

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with a domination number greater than the domination number of G . In this paper, we prove that b(G)⩽ min {8,Δ(G)+2} for a planar graph G and b(G)⩽3 for a graph G with forbidden minor K 4 .

We prove that a locally cobipartite graph on n vertices contains a family of at most n cliques that cover its edges. This is related to Opsut's conjecture that states the competition number of a locally cobipartite graph is at most two.

This paper establishes that a 3-connected graph G that has a triangle in which every single-edge contraction is 3-connected has a minor that uses the triangle and is isomorphic to K 5 or the octahedron.