Turán-type results for partial orders and intersection graphs of convex sets

We prove Ramsey-type results for intersection graphs of geometric objects. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c > 0 such that for every family F of n convex sets in the plane, the intersection graph of F or its complement contains a balanced complete bipartite graph of size at least cn. There is a constant c > 0 such that for every family F of n x-monotone curves in the plane, the intersection graph G of F contains a balanced complete bipartite graph of size at least cn/log n or the complement of G contains a balanced complete bipartite graph of size at least cn. Our bounds rely on new Turán-type results on incomparability graphs of partially ordered sets.     

Automorphism groups of graphs with forbidden subgraphs

For a graph Ф letF(Ф) be the class of finite graphs which do not contain an induced subgraph isomorphic to Ф. We show that whenever Ф is not isomorphic to a path on at most 4 vertices or to the complement of such a graph then for every finite groupG there exists a graph ГєF(Ф) such thatG is isomorphic to the automorphism group of Г. For all paths д on at most 4 vertices we determine the class of all automorphism groups of members ofF(д).     

Unitary units in modular group algebras of 2-groups

We study the unitary subgroupV _?(F₂ G) in the group algebras F₂ Gof 2-groups of maximal class over the field F₂of two elements. We show that there does not exist a normal complement to Gin V _?(F₂ G) if and only if Gis the dihedral group of order 2ⁿ(n≥ 5) or the semidihedral group of order 2ⁿ(n≥5). We also describe V _?(F₂ G) when the subgroup Ghas order 8 and 16 and in this case there exist a normal complement of Gin V _?(F₂ G).     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

Krull–Schmidt reduction of principal bundles in arbitrary characteristic

Let M be an irreducible projective variety defined over an algebraically closed field k, and let E_G be a principal G-bundle over M, where G is a connected reductive linear algebraic group defined over k. We show that for E_G there is a naturally associated conjugacy class of Levi subgroups of G. Given a Levi subgroup H in this conjugacy class, the principal G-bundle E_G admits a reduction of structure group to H. Furthermore, this reduction is unique up to an automorphism of E_G.     

On stability of the hamiltonian index under contractions and closures

The hamiltonian index of a graph G is the smallest integer k such that the k‐th iterated line graph of G is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an A_G(F)‐contractible subgraph F of a graph G nor the closure operation performed on G (if G is claw‐free) affects the value of the hamiltonian index of a graph G. AMS Subject Classification (2000): 05C45, 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.     

Colourings of the cartesian product of graphs and multiplicative Sidon sets

Let F be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph G with no bichromatic subgraph in F is F-free. The F-free chromatic number χ(G,F) of a graph G is the minimum number of colours in an F-free colouring of G. For appropriate choices of F, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies F-free colourings of the cartesian product of graphs.     

Subgraph‐avoiding coloring of graphs

Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}Given a “forbidden graph” F and an integer k, an F‐avoiding k‐coloring of a graph G is a k‐coloring of the vertices of G such that no maximal F‐free subgraph of G is monochromatic. The F‐avoiding chromatic number ac_F(G) is the smallest integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac_F(G) ? C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac_F(G) in terms of various invariants of G are also given. Particularly, we prove that ${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}$, where n is the order of G and F is not K_k or $\overline{{{K}}_{{{k}}}}$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300–310, 2010     

On holomorphic principal bundles over a compact Riemann surface admitting a flat connection

Let G be a connected reductive linear algebraic group over , and X a compact connected Riemann surface. Let be a Levi factor of some parabolic subgroup of G, with its maximal abelian quotient. We prove that a holomorphic G-bundle over X admits a flat connection if and only if for every such L and every reduction of the structure group of to L, the -bundle obtained by extending the structure group of is topologically trivial. For , this is a well-known result of A. Weil. Received: 1 December 2000 / Revised version: 2 April 2001 / Published online: 24 September 2001     

Unique and faithful embeddings of projective-planar graphs

A graph G is uniquely embeddable in a surface F² if for any two embeddings f₁,f₂: G → F², there exists an isomorphism σ: G → G and a homeomorphism h: F² → F² for which h → f₁ = f₂ σ. A graph G is faithfully embeddable in a surface F² if G admits an embedding f: G → F² such that for any isomorphism σ: G → G, there is a homeomorphism h: F² → F² with h → f = f → σ. It will be shown that if a projective-planar graph G is 5-connected and contains a subdivision of the complete graph K₆ as its subgraph, then G is uniquely embeddable in a projective plane, and that moreover if G is not isomorphic to K₆, then G is faithfully embeddable in a projective plane.     

Rank-perfect and" weakly rank-perfect graphs

An edge e of a perfect graph G is critical if G−e is imperfect. We would like to decide whether G−e is still “almost perfect” or already “very imperfect”. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.     

Graphs with Least Eigenvalue −2: The Star Complement Technique

Let G be a connected graph with least eigenvalue –2, of multiplicity k. A star complement for –2 in G is an induced subgraph H = G – X such that |X| = k and –2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of –2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.     

On brittle graphs

Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P₄ or not an endpoint of any P₄. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n₄) algorithm to recognize HHD-free graphs, and also an O(n₄) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n₄) time.     

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     

A complete solution to the infinite Oberwolfach problem

Let F be a 2‐regular graph of order v. The Oberwolfach problem, OP(F), asks for a 2‐factorization of the complete graph on v vertices in which each 2‐factor is isomorphic to F. In this paper, we give a complete solution to the Oberwolfach problem over infinite complete graphs, proving the existence of solutions that are regular under the action of a given involution free group G. We will also consider the same problem in the more general context of graphs F that are spanning subgraphs of an infinite complete graph $\mathbb{K}$ and we provide a solution when F is locally finite. Moreover, we characterize the infinite subgraphs L of F such that there exists a solution to OP(F) containing a solution to OP(L).     

Contact patterns of equal nonoverlapping spheres

LetF be a set of nonoverlapping spheres in Euclideann-spaceE ⁿ . By the contact pattern ofF we mean the graph whose vertex set isF and two vertices are adjacent whenever the corresponding spheres touch each other. Every graph turns out to be a contact pattern in some dimension. This paper studies the smallest dimensionn for a graphG such thatG is a contact pattern inE ⁿ . Among others, the smallest dimensions are determined for the join of a large complete graph and an empty graph, and for complete multipartite graphs with more vertex classes than the size of its largest vertex class.     

Strongly semistable bundles on a curve over a finite field

We show that a principal G-bundle on a smooth projective curve over a finite field is strongly semistable if and only if it is defined by a representation of the fundamental group scheme of the curve into G. Received: 24 April 2006