Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

A characterization of P4‐indifference graphs

A graph is a P₄‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a. P₄‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P₄‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999     

On the harmonious coloring of collections of graphs

The hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC-number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC-number of collections of paths and 4m-cycles. © 1995, John Wiley & Sons, Inc.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Closures,cycles, and paths

In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Hajós Theorem For Colorings Of Edge-Weighted Graphs

Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K _k by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101.     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Bipartite anti‐Ramsey numbers of cycles

We determine the maximum number of colors in a coloring of the edges of K_m,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of K_a,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a² ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

Geometric Achromatic and Pseudoachromatic Indices

The pseudoachromatic index of a graph is the maximum number of colors that can be assigned to its edges, such that each pair of different colors is incident to a common vertex. If for each vertex its incident edges have different color, then this maximum is known as achromatic index. Both indices have been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper we extend the notion of pseudoachromatic and achromatic indices for geometric graphs, and present results for complete geometric graphs. In particular, we show that for n points in convex position the achromatic index and the pseudoachromatic index of the complete geometric graph are \(\lfloor \frac{n^2+n}{4} \rfloor \).     

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.     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Dominator Colorings in Some Classes of Graphs

A dominator coloring is a coloring of the vertices of a graph such that every vertex is either alone in its color class or adjacent to all vertices of at least one other class. We present new bounds on the dominator coloring number of a graph, with applications to chordal graphs. We show how to compute the dominator coloring number in polynomial time for P ₄-free graphs, and we give a polynomial-time characterization of graphs with dominator coloring number at most 3.     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Almost all steinhaus graphs have diameter 2

A Steinhaus graph is a graph with n vertices whose adjacency matrix (a_{i, j}) satisfies the condition that a_{i, j} ? a_{a--1, j--1} + a _{i--1, j} (mod 2) for each 1 < i < j ≤ n. It is clear that a Steinhaus graph is determined by its first row. In [3] Bringham and Dutton conjecture that almost all Steinhaus graphs have diameter 2. That is, as n approaches infinity, the ratio of the number of Steinhaus graphs with n vertices having diameter 2 to the total number of Steinhaus graphs approaches 1. Here we prove Bringham and Dutton's conjecture.