Colouring Clique-Hypergraphs of Circulant Graphs

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, ${\mathcal{H}(G)}$ , of a graph G has V(G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of ${\mathcal{H}(G)}$ is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained.     

Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].     

Reconstructing a Graph from its Arc Incidence Graph

Introduced implicitly by Brualdi and Massey (Discret Math 122(1–3):51–58, 1993) in their work on the strong chromatic index of multigraphs, the arc incidence graph AI(G) of a graph G is defined as the square of the line graph of the incidence graph of G. We describe a linear-time algorithm for recognizing arc incidence graphs and reconstructing a graph with no isolated vertices from its arc incidence graph.     

A study of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a graph G is defined to have the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

The t-Tone Chromatic Number of Random Graphs

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ ₂(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.     

Graphs with a Minimal Number of Convex Sets

Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every u–v geodesic (i.e. shortest u–v path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced u–v path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.     

Score sequences in oriented graphs

An oriented graph is a digraph with no symmetric pairs of directed arcs and without loops. The score of a vertexv _i in an oriented graph D is $a_{v_i } $ (or simply a_i) $d_{v_i }^ - $ are the outdegree and indegree, respectively, ofv _i and n is the number of vertices in D. In this paper, we give a new proof of Avery’s theorem and obtain some stronger inequalities for scores in oriented graphs. We also characterize strongly transitive oriented graphs.     

Constructions of Large Graphs on Surfaces

We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k, determine the maximum order N(Δ,k,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs. Given a surface Σ of Euler genus g and an odd diameter k, the current best asymptotic lower bound for N(Δ,k,Σ) is given by $$\sqrt{\frac{3}{8}}g \Delta^{\lfloor k/2 \rfloor}.$$ Our constructions produce new graphs of order $$\left\{\begin{array}{ll}6 \Delta^{\lfloor k/2 \rfloor} \qquad \qquad \qquad \qquad {\rm if \Sigma\;is\;the\;Klein\;bottle} \\ \left(\frac{7}{2} + \sqrt{6g + \frac{1}{4}}\right) \Delta^{\lfloor k/2 \rfloor} \quad {\rm otherwise},\end{array}\right.$$ thus improving the former value.     

A Study of Monopolies in Graphs

In a graph G, a set D of vertices is said to be a monopoly if any vertex ${v\in V(G) \setminus D}$ has at least deg(v)/2 neighbors in D. A strict monopoly is defined similarly when we replace deg(v)/2 by deg(v)/2 + 1 for any vertex v whose degree is even number. By the monopoly size (resp. strict monopoly size) of G we mean the smallest cardinality of a monopoly (resp. strict monopoly) in G. We first discuss the basic bounds for the monopoly and strict monopoly size of graphs. In the second section we show relationships between matchings and monopolies and present some upper bounds for the monopoly and strict monopoly size of graphs in terms of the matching number of graphs. The third section is devoted to presenting some lower bounds for the monopoly size of graphs in terms of the even-girth and odd-girth of graphs.     

Degree Sum Conditions for Hamiltonicity on k-Partite Graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

On the Relaxed Colouring Game and the Unilateral Colouring Game

In the paper we introduce the new game—the unilateral \({\mathcal{P}}\) -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property \({\mathcal {P}}\) and a set C of r colours. In the unilateral \({\mathcal {P}}\) -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral \({\mathcal {P}}\) -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property \({\mathcal {P}}\) . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The \({\mathcal {P}}\) -unilateral game chromatic number, denoted by \({\chi_{ug}^\mathcal {P}(G)}\) , is the least number r for which Alice has a winning strategy for the unilateral \({\mathcal {P}}\) -colouring game with r colours on G. We prove that the \({\mathcal {P}}\) -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral \({\mathcal {P}}\) -colouring game. Moreover, for k ≥  2 we define a class of graphs \({\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}\) . The class \({\mathcal {H}_k }\) contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let \({\mathcal {S}_d}\) be the class of graphs with maximum degree at most d. We find the upper bound for the \({\mathcal {S}_2}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_3}\) and we study the \({\mathcal {S}_d}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_4}\) for \({d \in \{2,3\}}\) . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if \({G \in \mathcal {H}_k}\) , then \({\chi_g^{(d)}(G) \leq k + 2-d}\) , for \({k \in \{3, 4\}}\) and \({d \in \{0, \ldots, k-1\}}\) . This generalizes a known result for trees.     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

Minimal extensions of graphs to absolute retracts

A graph H is an absolute retract if for every isometric embedding h of, into a graph G an edge-preserving map g from G to H exists such that g · h is the identity map on H. A vertex v is embeddable in a graph G if G ? v is a retract of G. An absolute retract is uniquely determined by its set of embeddable vertices. We may regard this set as a metric space. We also prove that a graph (finite metric space with integral distance) can be isometrically embedded into only one smallest absolute retract (injective hull). All graphs in this paper are finite, connected, and without multiple edges.