Joins of n-degenerate graphs and uniquely (m,n)-partitionable graphs

The Lick-White point-partition numbers generalize the chromatic number and the point-arboricity. Similarly, uniquely (m, n)-partitionable graphs generalize uniquely m-colorable graphs.Theorem 1 gives a method for constructing uniquely (m, n)-partitionable graphs as well as a sufficient condition for a join of mn-degenerate graphs to be uniquely (m, n)-partitionable. For the case n = 1, we obtain a necessary and sufficient condition (Lemma 1). As a consequence, an embedding result for uniquely (m, 1)-partitionable graphs is obtained (Theorem 2). Finally, uniquely (m, n)-partitionable graphs with minimal connectivity are constructed (Theorem 3).     

r-tuple colorings of uniquely colorable graphs

An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs.     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

Uniquely colorable perfect graphs

This paper defines the concept of sequential coloring. If G or its complement is one of four major types of perfect graphs, G is shown to be uniquely k-colorable it and only if it is sequentially k-colorable. It is conjectured that this equivalence is true for all perfect graphs. A potential role for sequential coloring in verifying the Strong Perfect Graph Conjecture is discussed. This conjecture is shown to be true for strongly sequentially colorable graphs.     

Almost all k-colorable graphs are easy to color

We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k ≥ 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brélaz and justified on experimental grounds optimally colors almost all k-colorable graphs. Efficient implementations of both algorithms are given. The first one runs in O(n + m log k) time where n is the number of vertices and m the number of edges. The new implementation of Brélaz's algorithm runs in O(m log n) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs.     

Constructing Uniquely Realizable Graphs

In the Graph Realization Problem (GRP), one is given a graph  $G$ , a set of non-negative edge-weights, and an integer  $d$ . The goal is to find, if possible, a realization of  $G$ in the Euclidian space $\mathbb R ^d$ , such that the distance between any two vertices is the assigned edge weight. The problem has many applications in mathematics and computer science, but is NP-hard when the dimension  $d$ is fixed. Characterizing tractable instances of GRP is a classical problem, first studied by Menger in 1931. We construct two new infinite families of GRP instances which can be solved in polynomial time. Both constructions are based on the blow-up of fixed small graphs with large expanders. Our main tool is the Connelly’s condition in Rigidity Theory, combined with an explicit construction and algebraic calculations of the rigidity (stress) matrix. As an application of our results, we describe a general framework to construct uniquely k-colorable graphs. These graphs have the extra property of being uniquely vector k-colorable. We give a deterministic explicit construction of such a family using Cayley expander graphs.     

Coloring graphs with crossings

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K₆ as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.     

On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n), and we conjecture that our upper bound ⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Almost all graphs with 1.44n edges are 3-colorable

We establish a uniform asymptotic approximation of certain probabilities arising in the coupon collector's problem. Then we use this approximation to prove that almost all graphs with n vertices and 1.44 n edges contain no subgraph with minimum degree at least three, and hence are 3-colorable.     

Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.     

5-Chromatic even triangulations on surfaces

A triangulation is said to be even if each vertex has even degree. It is known that every even triangulation on any orientable surface with sufficiently large representativity is 4-colorable [J. Hutchinson, B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory, Ser. B 84 (2002) 225-239], but all graphs on any surface with large representativity are 5-colorable [C. Thomassen, Five-coloring maps on surfaces, J. Combin Theory Ser. B 59 (1993) 89-105]. In this paper, we shall characterize 5-chromatic even triangulations with large representativity, which appear only on nonorientable surfaces.     

Pairs of Chromatically Equivalent Graphs

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. In this paper we give the means to construct infinitely many pairs of chromatically equivalent graphs where one graph in the pair is clique-separable, that is, can be obtained by identifying an r-clique in some graph H ₁ with an r-clique in some graph H ₂, and the other graph is non-clique-separable. There are known methods for finding pairs of chromatically equivalent graphs where both graphs are clique-separable or both graphs are non-clique-separable. Although examples of pairs of chromatically equivalent graphs where only one of the graphs is clique-separable are known, a method for the construction of infinitely many such pairs was not known. Our method constructs such pairs of graphs with odd order n ≥ 9.     

Terwilliger graphs with μ ≤ 3

A Terwilliger graph is a noncomplete graph in which the intersection of the neighborhoods of any two vertices at distance 2 from each other is a μ-clique. We classify connected Terwilliger graphs with μ = 3 and describe the structure of Terwilliger graphs of diameter 2 with μ = 2.     

Construction of uniquely H‐colorable graphs

We shall prove that for any graph H that is a core, if χ(G) is large enough, then H × G is uniquely H‐colorable. We also give a new construction of triangle free graphs, which are uniquely n‐colorable. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 1–6, 1999     

Very large cliques are easy to detect

It is known that, for every constant k?3, the presence of a k-clique (a complete sub-graph on k vertices) in an n-vertex graph cannot be detected by a monotone boolean circuit using much fewer than n^k gates. We show that, for every constant k, the presence of an (n-k)-clique in an n-vertex graph can be detected by a monotone circuit using only a logarithmic number of fanin-2 OR gates; the total number of gates does not exceed O(n²logn). Moreover, if we allow unbounded fanin, then a logarithmic number of gates is enough.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

Kneser's conjecture,chromatic number,and homotopy

If the simplicial complex formed by the neighborhoods of points of a graph is (k ? 2)-connected then the graph is not k-colorable. As a corollary Kneser's conjecture is proved, asserting that if all n-subsets of a (2n ? k)-element set are divided into k + 1 classes, one of the classes contains two disjoint n-subsets.