Search

For d > 0 , define G (Q 3 , d) to be the graph whose set of vertices is the rational space Q 3 , where two vertices are adjacent if and only if they are a Euclidean distance d apart. Let χ (Q 3 , d) be the chromatic number of such a graph or, in other words, the minimum number of colors needed to color the points of Q 3 so that no two points at distance d apart receive the same color. An open problem, originally posed by Benda and Perles in the 1970s, asks if there exists d such that χ (Q 3 , d) = 3. Through numerous efforts over the years, χ (Q 3 , d) has been determined for many values of d , and for all those distances d where χ (Q 3 , d) has not been exactly pinned down, it is known that χ (Q 3 , d) ∈ { 3 , 4 }. In our work, we detail several search algorithms we have employed to find 4-chromatic subgraphs of various graphs G (Q 3 , d) whose chromatic number was previously unknown. Ultimately, we conjecture that no 3-chromatic G (Q 3 , d) exists. Along the way, we pose a few related questions that we feel are of interest in their own right. [ABSTRACT FROM AUTHOR]

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v0 → v1 → ... → vk either there is no arc between v0 and vk, or vi → vj is an arc for all 0 ≤ i < j ≤ k. An undirected graph is semitransitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via Erdős' theorem by Halldórsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the triangle-free Kneser graph K(8, 3) is not semi-transitive, and have raised the question on the existence of smaller triangle-free nonsemi- transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Grötzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chvátal graph) are not semi-transitive. Hence, the Gr¨otzsch graph is the smallest trianglefree non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph C(13; 1, 5) on 13 vertices) and dense ones (Toft's graphs). Finally, we show that each 4-regular circulant graph (possibly containing triangles) is semi-transitive. [ABSTRACT FROM AUTHOR]

The Babai numbers and the upper chromatic number are parameters that can be assigned to any metric space. They can, therefore, be assigned to any connected simple graph. In this paper we make progress in the theory of the first Babai number and the upper chromatic number in the simple graph setting, with emphasis on graphs of diameter 2. [ABSTRACT FROM AUTHOR]

In this paper we find the matching polynomial for some well known graphs such as Chvatal graph, Grotzsch graph, Bidiakis cube, Bislit cube, Soifer graph, Fritsch graph and also we discuss recurrence relations for triangular book graph, fan graph and star related graphs. Moreover we discuss the relation between the matching polynomial of fan graph Fmn for m=1 and m = 2. [ABSTRACT FROM AUTHOR]

There are infinite sequences of graphs { G} where | G| = n such that the minimal dominating sets for G × H fall into predictable patterns, in light of which γ ( G × H) may be nearly linear in n; the coefficient of linearity may be regarded as the average density of the dominating set in the H-fibers of the product. The specific cases where the sequence { G} consists of cycles or path is explored in detail, and the domination density of the Grötzsch graph is calculated. For several other sequences { G}, the limit of this density can be seen to exist; in other cases the ratio $${\frac{\gamma (G_n \times H)}{\gamma (G_n)}}$$ proves to be of greater interest, and also exists for several families of graphs. [ABSTRACT FROM AUTHOR]