Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

The Chartrand-Schuster conjecture: Graphs with unique distance trees are regular

Let G be a finite connected graph with no cut vertex. A distance tree T is a spanning tree of G which further satisfies the condition that for some vertex v, d_G(v, u) = d_T(v, u) for all u, where d_G(v, u) denotes the distance of u from v in the graph G. The conjecture that if all distance trees of G are isomorphic to each other then G is a regular graph, is settled affirmatively. The conjecture was made by Chartrand and Schuster.     

A note on list improper coloring of plane graphs

A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G). An (L,d)^∗-coloring is a mapping ? that assigns a color ?(v)∈L(v) to each vertex v∈V(G) such that at most d neighbors of v receive color ?(v). A graph is called (k,d)^∗-choosable, if G admits an (L,d)^∗-coloring for every list assignment L with |L(v)|≥k for all v∈V(G). In this note, it is proved that every plane graph, which contains no 4-cycles and l-cycles for some l∈{8,9}, is (3,1)^∗-choosable.     

On bounds for the cutting number of a graph

The cutting number of a vertex v of a finite graph G = (V,E) is a natural measure of the extent to which the removal of v disconnects the graph. Precisely, the cutting number c(v) of v is defined as the number of pairs of vertices {u,w} of G such that u,w ≠ v and every u-w path contains v. The cutting number c(G) of G is the maximum value of c(v) over all vertices in V. We provide exact bounds on the cutting number of G in terms of order and diameter of the graph.     

Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.     

On intransitive graph-restrictive permutation groups

Let Γ be a finite connected G-vertex-transitive graph and let v be a vertex of Γ. If the permutation group induced by the action of the vertex-stabiliser G _v on the neighbourhood Γ(v) is permutation isomorphic to L, then (Γ,G) is said to be locally L. A permutation group L is graph-restrictive if there exists a constant c(L) such that, for every locally L pair (Γ,G) and a vertex v of Γ, the inequality |G _v |≤c(L) holds. We show that an intransitive group is graph-restrictive if and only if it is semiregular.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

Bordeaux 3-color conjecture and 3-choosability

A graph G=(V,E) is list L-colorable if for a given list assignment L={L(v):v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27].     

Diameter-essential edges in a graph

The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)<diam(G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G).     

Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K₂∪(n−2)K₁, P₄∪(n−4)K₁, and C₅∪(n−5)K₁. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.     

k-fold coloring of planar graphs

A k-fold n-coloring of G is a mapping φ: V (G) → Zk(n) where Zk(n) is the collection of all ksubsets of {1,2,...,n} such that φ(u) ∩φ(v) = φ if uv ∈ E(G).If G has a k-fold n-coloring,i.e.,G is k-fold n-colorable.Let the smallest integer n such that G is k-fold n-colorable be the k-th chromatic number,denoted by χk(G).In this paper,we show that any outerplanar graph is k-fold 2k-colorable or k-fold χk(C*)-colorable,where C* is a shortest odd cycle of G.Moreover,we investigate that every planar graph with odd girth at least 10k-9(k 3) can be k-fold (2k + 1)-colorable.     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).     

The eccentric connectivity index of nanotubes and nanotori

Let G be a molecular graph. The eccentric connectivity index ξ^c(G) is defined as ξ^c(G)=∑_u∈V(G)deg_G(u)ε_G(u), where deg_G(u) denotes the degree of vertex u and ε_G(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC₄C₈(S) nanotube and TC₄C₈(S) nanotorus are given.     

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).     

Homomorphisms from sparse graphs to the Petersen graph

Let G be a graph and let c: be an assignment of 2-elements subsets of the set {1,…,5} to the vertices of G such that for any two adjacent vertices u and v,c(u) and c(v) are disjoint. Call such a coloring c a (5, 2)-coloring of G. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph.The maximum average degree of G is defined as . In this paper, we prove that every triangle-free graph with is homomorphic to the Petersen graph. In other words, such a graph is (5, 2)-colorable. Moreover, we show that the bound on the maximum average degree in our result is best possible.     

On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvo?ák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem of finding a coloring of G from a given list L to the problem of finding a “large” independent set in the auxiliary graph H(G,L) with vertex set {(v, c): v ∈ V (G) and c ∈ L(v)}. It is similar to the old reduction by Plesnevi? and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G□K _k, but DP-coloring seems more promising and useful than the Plesnevi?–Vizing reduction. Some properties of the DP-chromatic number χ _DP (G) resemble the properties of the list chromatic number χ _l (G) but some differ quite a lot. It is always the case that χ _DP (G) ≥ χ _l (G). The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erd?s–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in n-vertex graphs critical with respect to DP-coloring.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

On <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings of nearly bipartite graphs

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A g _c -coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The g _c -chromatic index of G, denoted by χ′g _c (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the g _c -chromatic index equal to δ _g (G) or δ _g (G) ? 1, where \({\delta _g}\left( G \right) = \mathop {\min }\limits_{v \in V\left( G \right)} \left\lfloor {d\left( v \right)/g\left( v \right)} \right\rfloor \). A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G ? u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′g _c (G) = δ _g (G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.     

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.