On Turan hypergraphs

Let α(H) be the stability number of a hypergraph H = (X, $\text{E}$). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ? α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ?α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs.     

Restricted coloring problems on Graphs with few P 4’s

In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P ₄-tidy graphs and (q, q ? 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q ? 4 distinct P ₄’s. These classes include cographs and P ₄-sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P ₄-tidy graphs and connected (q, q ? 4)-graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter q(G), which is the minimum q such that G is a (q, q ? 4)-graph. We also prove that every connected (q, q ? 4)-graph with at least q vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive, generalizing the main result of Lyons (2011).     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

On coloring graphs with locally small chromatic number

In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc _k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc _k n ^1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc _k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Total chromatic number of one kind of join graphs

The total chromatic number χ_T(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χ_T(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph K_n1,n2 and a path P_m is of Type 1.     

Ordering trees with n vertices and matching number q by their largest Laplacian eigenvalues

Denote by T_n,q the set of trees with n vertices and matching number q. Guo [On the Laplacian spectral radius of a tree, Linear Algebra Appl. 368 (2003) 379-385] gave the tree in T_n,q with the greatest value of the largest Laplacian eigenvalue. In this paper, we give another proof of this result. Using our method, we can go further beyond Guo by giving the tree in T_n,q with the second largest value of the largest Laplacian eigenvalue.     

Set-coloring of Edges and Multigraph Ramsey Numbers

Edge-colorings of multigraphs are studied where a generalization of Ramsey numbers is given. Let ${M_n^{(r)}}$ be the multigraph of order n, in which there are r edges between any two different vertices. Suppose q ₁, q ₂, . . . , q _k and r are positive integers, and q _i ≥ 2(1 ≤ i ≤ k), k > r. Let the multigraph Ramsey number ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ be the minimum positive integer n such that in any k-edge coloring of ${M_n^{(r)}}$ (every edge is colored with one among k given colors, and edges between the same pair of vertices are colored with different colors), there must be ${i \in \{1,2,\ldots,k\}}$ such that ${M_n^{(r)}}$ has such a complete subgraph of order q _i , of which all the edges are in color i. By Ramsey’s theorem it is easy to show ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ exists for given q ₁ ,q ₂, . . . , q _k and r. Lower and upper bounds for some multigraph Ramsey numbers are given.     

On the chromaticity of the 2-degree integral subgraph ofq-trees

A graphG is called to be a 2-degree integral subgraph of aq-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactlyq- 1 triangles. An added-vertexq-treeG with n vertices is obtained by taking two verticesu, v (u, v are not adjacent) in a q-treesT withn -1 vertices such that their intersection of neighborhoods ofu, v forms a complete graphK _q , and adding a new vertexx, new edgesxu, xv, xv ₁,xv ₂, …,xv _{q- 4}, where {v ₁,v ₂,...,v _q?4} ?-K _q . In this paper we prove that a graphG with minimum degree not equal toq -3 and chromatic polynomialP(G;λ) = λ(λ - 1) … (λ -q +2)(λ -q +1)³(λ -q) ^{n- q- 2} withn ≥ q + 2 has and only has 2-degree integral subgraph of q-tree withn vertices and added-vertex q-tree withn vertices.     

The equitable total chromatic number of the graphHM(W n )

The equitable total chromatic number _Χet (G) of a graphG is the smallest integerk for whichG has a total k-coloring such that the number of vertices and edges in any two color classes differ by at most one. In this paper, we determine the equitable total chromatic number of one class of the graphs.     

Non-orientable fundamental surfaces in lens spaces

We give a concrete example of an infinite sequence of (pn,qn)-lens spaces L(pn,qn) with natural triangulations T(pn,qn) with pn tetrahedra such that L(pn,qn) contains a certain non-orientable closed surface which is fundamental with respect to T(pn,qn) and of minimal crosscap number among all closed non-orientable surfaces in L(pn,qn) and has n−2 parallel sheets of normal disks of a quadrilateral type disjoint from the pair of core circles of L(pn,qn). Actually, we can set p₀=0, q₀=1, pk+1=3pk+2qk and qk+1=pk+qk.     

A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2

The upper chromatic number of a hypergraph H=(X,E) is the maximum number k for which there exists a partition of X into non-empty subsets X=X₁∪X₂∪?∪X_k such that for each edge at least two vertices lie in one of the partite sets. We prove that for every n?3 there exists a 3-uniform hypergraph with n vertices, upper chromatic number 2 and ⌈n(n-2)/3⌉ edges which implies that a corresponding bound proved in [K. Diao, P. Zhao, H. Zhou, About the upper chromatic number of a co-hypergraph, Discrete Math. 220 (2000) 67-73] is best-possible.     

Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

A result on the total colouring of powers of cycles

The total chromatic number χ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that for every simple graph G, χ_T(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.     

deBruijn-like sequences and the irregular chromatic number of paths and cycles

A deBruijn sequence of orderk, or a k-deBruijn sequence, over an alphabet A is a sequence of length |A|^k in which the last element is considered adjacent to the first and every possible k-tuple from A appears exactly once as a string of k-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like if for some k, each of the consecutive k-element substrings is distinct.A vertex coloring χ:V(G)→[k] of a graph G is said to be proper if no pair of adjacent vertices in G receive the same color. Let C(v;χ) denote the multiset of colors assigned by a coloring χ to the neighbors of vertex v. A proper coloring χ of G is irregular if χ(u)=χ(v) implies that C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color G is called the irregular chromatic number of G. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of C_n and P_n for n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.     

Chromatic capacity and graph operations

The chromatic capacityχ_cap(G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f:N→N such that χ_cap(G)?f(χ(G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k?n/2 there exists a graph G with χ(G)=n and χ_cap(G)=n-k, extending a result of Greene. We obtain bounds on that are tight as r→∞, where is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χ_cap(G)+1=χ(G)=p that contains no odd cycles of length less than q.     

The game chromatic number of random graphs

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number χ_g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph G_n,p. We show that with high probability, the game chromatic number of G_n,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008