Local condition for planar graphs of maximum degree 7 to be 8-totally colorable

The total chromatic number of a graph G, denoted by χ^″(G), is the minimum number of colors needed to color the vertices and edges of G such that no two adjacent or incident elements get the same color. It is known that if a planar graph G has maximum degree Δ≥9, then χ^″(G)=Δ+1. In this paper, we prove that if G is a planar graph with maximum degree 7, and for every vertex v, there is an integer k_v∈{3,4,5,6} so that v is not incident with any k_v-cycle, then χ^″(G)=8.     

On the b-continuity property of graphs

This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic numberb(G) of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using χ(G) colors.We say that G is b-continuous iff for each k, χ(G)?k?b(G), there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrumS_b(G) of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using χ(G) and b(G) colors are given.     

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.     

Dynamic list coloring of bipartite graphs

A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of G, denoted by χ₂(G), is called the dynamic chromatic number of G. The least integer k, such that if every vertex of G is assigned a list of k colors, then G has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of G, denoted by ch(G) (resp. the dynamic choice number, denoted by ch₂(G)). It was recently conjectured (Akbari et al. (2009) [1]) that for any graph G, ch₂(G)=max(ch(G),χ₂(G)). In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph G with ch(G)=χ₂(G)=3 and ch₂(G)=4. Then, for any integer k≥5, we construct a bipartite graph G_k such that ch(G_k)=χ₂(G_k)=3 and ch₂(G)≥k.     

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.     

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition r^p(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex.     

A Generalization of the Gallai–Roy Theorem

 A well-known and essential result due to Roy ([4], 1967) and independently to Gallai ([3], 1968) is that if D is a digraph with chromatic number χ(D), then D contains a directed path of at least χ(D) vertices. We generalize this result by showing that if ψ(D) is the minimum value of the number of the vertices in a longest directed path starting from a vertex that is connected to every vertex of D, then χ(D) ≤ψ(D). For graphs, we give a positive answer to the following question of Fajtlowicz: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ(G) colors and for any vertex v∈V(G), there is a path P starting at v which represents all χ(G) colors. Received: May 20, 1999 Final version received: December 24, 1999     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

Parity vertex coloring of outerplane graphs

A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χ_p(G).In this paper we prove that χ_p(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χ_p(G)=10. If a 2-connected outerplane graph G is bipartite, then χ_p(G)≤8, moreover, this bound is best possible.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Efficient algorithms for decomposing graphs under degree constraints

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d(v)?a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that d_A(v)?a(v) for every v∈A and d_B(v)?b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v)?a+b (a,b?1) or just d(v)?a+b-1 (a,b?2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.     

Color degree and alternating cycles in edge-colored graphs

Let G be an edge-colored graph. An alternating cycle of G is a cycle of G in which any two consecutive edges have distinct colors. Let d^c(v), the color degree of a vertex v, be defined as the maximum number of edges incident with v that have distinct colors. In this paper, we study color degree conditions for the existence of alternating cycles of prescribed length.     

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.     

The Erd?s-Lovász Tihany conjecture for quasi-line graphs

Erd?s and Lovász conjectured in 1968 that for every graph G with χ(G)>ω(G) and any two integers s,t≥2 with s+t=χ(G)+1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S])≥s and χ(G[T])≥t. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.     

Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

Let G be a connected graph, suppose that v is a vertex of G, and denote the subgraph formed from G by deleting vertex v by G?v. Denote the algebraic connectivities of G and G?v by α(G) and α(G?v), respectively. In this paper, we consider the functions ?(v)=α(G)−α(G?v) and , provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds. The function κ yields a measure of vertex centrality, and we apply that measure to analyse certain graphs arising from food webs.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

The 2-extendability of 5-connected graphs on surfaces with large representativity

A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F², except the sphere, is 2-extendable if ρ(G)?7−2χ(F²), where ρ(G) stands for the representativity of G on F² and χ(F²) for the Euler characteristic of F².     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.