Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

K6‐minors in triangulations and complete quadrangulations

In this paper, we shall prove that a projective‐planar (resp., toroidal) triangulation G has K₆ as a minor if and only if G has no quadrangulation isomorphic to K₄ (resp., K₅ ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective‐planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302‐312, 2009     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Toroidal graphs containing neither nor 6‐cycles are 4‐choosable

The choosability of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that , and if and only if G contains K₇. Cai et al. (J Graph Theory 65(1) (2010), 1–15) proved that a toroidal graph G without 7‐cycles is 6‐choosable, and if and only if G contains K₆. They also proved that a toroidal graph G without 6‐cycles is 5‐choosable, and conjectured that if and only if G contains K₅. We disprove this conjecture by constructing an infinite family of non‐4‐colorable toroidal graphs with neither K₅ nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither (a K₅ missing one edge) nor 6‐cycles are 4‐choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4‐choosable.     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

On perfect Γ‐decompositions of the complete graph

Generalizing the well‐known concept of an i‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph K_v to be i‐perfect if for every edge [x, y] of K_v there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a Γ‐decomposition (Γ‐factorization) of K_v that is i‐perfect for any i not exceeding the diameter of a connected graph Γ will be said a Steiner (Kirkman) Γ‐system of order v. In this article we first observe that as a consequence of the deep theory on decompositions of edge‐colored graphs developed by Lamken and Wilson [Lamken and Wilson, 2000, J Combin Theory Ser A 89, 149–200], there are infinitely many values of v for which there exists an i‐perfect Γ‐decomposition of K_v provided that Γ is an i‐equidistance graph, namely a graph such that the number of pairs of vertices at distance i is equal to the number of its edges. Then we give some concrete direct constructions for elementary abelian Steiner Γ‐systems with Γ the wheel on 8 vertices or a circulant graph, and for elementary abelian 2‐perfect cube‐factorizations. We also present some recursive constructions and some results on 2‐transitive Kirkman Γ‐systems. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 197–209, 2009     

Archimedean ϕ ‐tolerance graphs

Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval I_υ and a positive tolerance t_υ so that xy ∈ E ? | I_x ∩ I_y|≥ ? (t_x,t_y). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K_2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?_G‐tolerance graph for some Archimedean polynomial ?_G. Finally, we prove that there is a ?universal”? Archimedean function ? ^* such that every graph G is a ?^*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002     

Large set of P3‐decompositions

Let G=(V(G),E(G)) be a graph. A (n,G, λ)‐GD is a partition of the edges of λK_n into subgraphs (G‐blocks), each of which is isomorphic to G. The (n,G,λ)‐GD is named as graph design for G or G‐decomposition. The large set of (n,G,λ)‐GD is denoted by (n,G,λ)‐LGD. In this work, we obtain the existence spectrum of (n,P₃,λ)‐LGD. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 151–159, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10008     

List Colorings of K5‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K₅‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[S_k], where S_k: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(S_k) in G between the components of G[S_k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012     

K4−‐factor in a graph

Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K₄^?‐factor (K₄^? is the graph obtained from K₄ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

The A4‐structure of a graph

We define the A₄‐structure of a graph G to be the 4‐uniform hypergraph on the vertex set of G whose edges are the vertex subsets inducing 2K₂, C₄, or P₄. We show that perfection of a graph is determined by its A₄‐structure. We relate the A₄‐structure to the canonical decomposition of a graph as defined by Tyshkevich [Discrete Math 220 (2000) 201–238]; for example, a graph is indecomposable if and only if its A₄‐structure is connected. We also characterize the graphs having the same A₄‐structure as a split graph.     

Nilpotent 1‐factorizations of the complete graph

For which groups G of even order 2n does a 1‐factorization of the complete graph K_2n exist with the property of admitting G as a sharply vertex‐transitive automorphism group? The complete answer is still unknown. Using the definition of a starter in G introduced in 4 , we give a positive answer for new classes of groups; for example, the nilpotent groups with either an abelian Sylow 2‐subgroup or a non‐abelian Sylow 2‐subgroup which possesses a cyclic subgroup of index 2. Further considerations are given in case the automorphism group G fixes a 1‐factor. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Nonseparating K4‐subdivisions in graphs of minimum degree at least 4

We first prove that for every vertex x of a 4‐connected graph G, there exists a subgraph H in G isomorphic to a subdivision of the complete graph K₄ on four vertices such that is connected and contains x. This implies an affirmative answer to a question of Kühnel whether every 4‐connected graph G contains a subdivision H of K₄ as a subgraph such that is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4‐connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredient of the proof where 4‐connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4 by developing the respective motor, a structure theorem for the class of simple connected graphs of minimum degree at least 4. A simple connected graph G of minimum degree 4 cannot be reduced to a smaller such graph by deleting a single edge or contracting a single edge and simplifying if and only if it is the square of a cycle or the edge disjoint union of copies of certain bricks as follows: Each brick is isomorphic to K₃, K₅, K_{2, 2, 2}, , , or one the four graphs , , , obtained from K₅ and K_{2, 2, 2} by deleting the edges of a triangle, or replacing a vertex x by two new vertices and adding four edges to the endpoints of two disjoint edges of its former neighborhood, respectively. Bricks isomorphic to K₅ or K_{2, 2, 2} share exactly one vertex with the other bricks of the decomposition, vertices of degree 4 in any other brick are not contained in any further brick of the decomposition, and the vertices of a brick isomorphic to K₃ must have degree 4 in G and have pairwise no common neighbors outside that brick.     

On large sets of Pk‐decompositions

Let G = (V(G),E(G)) be a graph. A (ν, G, λ)‐GD is a partition of all the edges of λK_ν into subgraphs (G‐blocks), each of which is isomorphic to G. The (ν, G, λ)‐GD is named as graph design for G or G‐decomposition. The large set of (ν, G, λ)‐GD is denoted by (ν, G, λ)‐LGD. In this paper, we obtain a general result by using the finite fields, that is, if q ≥ k ≥ 2 is an odd prime power, then there exists a (q,P_k, k ? 1)‐LGD. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Finding paths between 3‐colorings

Given a 3‐colorable graph G together with two proper vertex 3‐colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are proper 3‐colorings? We prove that this question is answerable in polynomial time. We do so by characterizing the instances G, α, β where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between α and β, or exhibits a structure which proves that no such sequence exists. In the case that a sequence of recolorings does exist, the algorithm uses O(|V(G)|²) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, α, β that require Ω(|V(G)|²) recoloring steps. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 69‐82, 2011     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Nondisconnecting disentanglements of amalgamated 2‐factorizations of complete multipartite graphs

In this paper necessary and sufficient conditions are found for an edge‐colored graph H to be the homomorphic image of a 2‐factorization of a complete multipartite graph G in which each 2‐factor of G has the same number of components as its corresponding color class in H. This result is used to completely solve the problem of finding hamilton decompositions of K_a,b ? E(U) for any 2‐factor U of K_a,b. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 460–467, 2001     

Perfect coloring and linearly χ‐bound P6‐free graphs

We derive decomposition theorems for P₆, K₁ + P₄‐free graphs, P₅, K₁ + P₄‐free graphs and P₅, K₁ + C₄‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, P_n (C_n) denotes the path (cycle) on n vertices and K₁ + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P₅, C₄‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 11 , Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007