A note on the line-distinguishing chromatic number and the chromatic index of a graph

Let λ(G) be the line-distinguishing chromatic number and x′(G) the chromatic index of a graph G. We prove the relation λ(G) ≥ x′(G), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.     

The star chromatic number of a graph

We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.     

On the fractional chromatic index of a graph and its complement

Jensen and Toft conjectured that for a graph with an even number of vertices, either the minimum number of colours in a proper edge colouring is equal to the maximum vertex degree, or this is true in its complement. We prove a fractional version of this conjecture.     

The strong chromatic number of a graph

It is shown that there is an absolute constant c with the following property: For any two graphs G₁ = (V, E₁) and G₂ = (V, E₂) on the same set of vertices, where G₁ has maximum degree at most d and G₂ is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = (V, E₁ U E₂) is precisely cd. The proof is based on probabilistic arguments.     

The chromatic covering number of a graph

Following [1], we investigate the problem of covering a graph G with induced subgraphs G₁,…, G_k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G_i's containing u is at least 1. The existence of such “chromatic coverings” provides some bounds on the chromatic number of G. © 2005 Wiley Periodicals, Inc.     

The chromatic difference sequence of a graph

Let α_k(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set α_k(G)=α_k(G)?α_(k?1)(G). The sequence a₁(G), a₂(G),… is called the chromatic difference sequence of the graph G. We present necessary and sufficient conditions for a sequence to be the chromatic difference sequence of some 4-colorable graph.     

The odd-valued chromatic polynomial of a signed graph

For a signed graph $\mathrm{\Sigma }=(G,\sigma )$, Zaslavsky defined a proper coloring on Σ and showed that the function counting the number of such colorings is a quasi-polynomial with period two, that is, a pair of polynomials, one for odd values and the other for even values. In this paper, we focus on the case of odd, written as $\chi (\mathrm{\Sigma },x)$ for short. We initially give a homomorphism expression of such colorings, by which the symmetry is considered in counting the number of homomorphisms. Besides, the explicit formulas $\chi (\mathrm{\Sigma },x)$ for some basic classes of signed graphs are presented. As a main result, we give a combinatorial interpretation of the coefficients in $\chi (\mathrm{\Sigma },x)$ and present several applications. In particular, the constant term in $\chi (\mathrm{\Sigma },x)$ gives a new criterion for balancing and a characterization for unbalanced unicyclic graph. At last, we also give a tight bound for the constant term of $\chi (\mathrm{\Sigma },x)$.     

The chromatic numbers of double coverings of a graph

If we fix a spanning subgraph H of a graph G, we can define a chromatic number of H with respect to G and we show that it coincides with the chromatic number of a double covering of G with co-support H. We also find a few estimations for the chromatic numbers of H with respect to G.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

The chromatic polynomial of an unlabeled graph

We investigate the chromatic polynomial χ(G, λ) of an unlabeled graph G. It is shown that $\text{χ(G, λ) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{χ(g, π, λ)}$, where g is any labeled version of G, A(g) is the automorphism group of g and χ(g, π, λ) is the chromatic polynomial for colorings of g fixed by π. The above expression shows that χ(G, λ) is a rational polynomial of degree n = |V(G)| with leading coefficient $\text{1}\text{|A(g)|}$. Though χ(G, λ) does not satisfy chromatic reduction, each polynomial χ(g, π, λ) does, thus yielding a simple method for computing χ(G, λ). We also show that the number N(G) of acyclic orientations of G is related to the argument λ = ?1 by the formula $\text{N(G) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{(?1)}{}^{\mathrm{s(\pi )}}\text{χ(g, π, ?1)}$, where s(π) is the number of cycles of π. This information is used to derive Robinson's (“Combinatorial Mathematics V” (Proc. 5th Austral. Conf. 1976), Lecture Notes in Math. Vol. 622, pp. 28–43, Springer-Verlag, New York/Berlin, 1977) cycle index sum equations for counting unlabeled acyclic digraphs.     

The cochromatic index of a graph

We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′(G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent.Several bounds for z′(G) are discussed. For example, it is shown that δ(G) - 1 ? z′(G)? Δ(G) + 1, with the lower bound being attained only for a complete graph. Here δ(G) and Δ(G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs.Given a graph G define a sequence of graphs G₀, G₁,…, G_k, with G₀=G and

, with k being the first value of i for which G_i is regular. Let φ_i(G) = |V(G) – V(G_i| + Δ (G_i) and setφ(G) = min_0?i?kφ_i(G). We show that φ(G) ? 1 ?z′(G)?φ(G) + 1. We then s that a graph G is of class A, B or C, if z′(G) = φ(G) ? 1, φ(G), orφ(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B.Finally, we show that if a, b and c are positive integers with a?b?c + 1 and a?c, then unless a = c = b - 1 = 1, there exists a graph G having δ(G) = a, Δ(G) =c, and z′(G) = b.     

The imbedding index of a graph

The natural extension of MacLane's combinatorial approach to planar imbeddings is seen to yield a combinatorial formulation of imbedding of a graph in a pseudosurface. This leads to a combinatorially defined parameter for all graphs, called the imbedding index. A generalization of the Heaword inequality is then proved for this parameter.     

The edge-Wiener index of a graph

If G is a connected graph, then the distance between two edges is, by definition, the distance between the corresponding vertices of the line graph of G. The edge-Wiener index W_e of G is then equal to the sum of distances between all pairs of edges of G. We give bounds on W_e in terms of order and size. In particular we prove the asymptotically sharp upper bound for graphs of order n.     

The Peterson recurrence formula for the chromatic discriminant of a graph

The absolute value of the coefficient of q in the chromatic polynomial of a graph G is known as the chromatic discriminant of G and is denoted α(G). There is a well known recurrence formula for α(G) that comes from the deletion-contraction rule for the chromatic polynomial. In this paper we prove another recurrence formula for α(G) that comes from the theory of Kac- Moody Lie algebras. We start with a brief survey on many interesting algebraic and combinatorial interpretations of α(G). We use two of these interpretations (in terms of acyclic orientations and spanning trees) to give two bijective proofs for our recurrence formula of α(G).     

New parameters involving chromatic sum in a graph

In this paper, we introduce four parameters which involve chromatic sum and independent domination. Corresponding to the chromatic sum coloring of G, the chromatic domination number, chromatic sum edge stability number, chromatic sum bondage number and domination chromatic sum color number are defined and studied.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

The chromatic class and the location of a graph on a closed surface

Sufficient conditions are obtained for the equality of the chromatic class of a graph to its maximal degree. These conditions are in terms of properties of the graph related to the possibility of its being located on a surface with certain topological properties.Translated from Matematicheskie Zametki, Vol. 7, No. 6, pp. 671–681, June, 1970.