A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable

A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ'(G) is the smallest integer k such that G has a total k-coloring. 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 8 and without a fan of four adjacent 3-cycles, then χ'(G) = 9.     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

Concise proofs for adjacent vertex-distinguishing total colorings

Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χ_at(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χ_at(G) when G is a complete graph or a cycle.     

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.     

Total chromatic number of graphs with small genus

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with k colors. Denote χ_ve (G) the total chromatic number of G, and c(Σ) the Euler characteristic of a surfase Σ. In this paper, we prove that for any simple graph G which can be embedded in a surface Σ with Euler characteristic c(Σ), χ_ve (G) = Δ (G) + 1 if c(Σ) > 0 and Δ (G) ≥ 13, or, if c(Σ) = 0 and Δ (G) ≥ 14. This result generalizes results in [3], [4], [5] by Borodin.     

Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz

Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.     

On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results

A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, χ_D(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n³log³n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number.     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

Injective coloring of planar graphs

A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχ_i(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χ_i(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χ_i(G)≤Δ+1 if g≥11; (3) χ_i(G)≤Δ+2 if g≥8.     

The Chromatic Index of a Graph Whose Core is a Cycle of Order at Most 13

Let G be a graph. The core of G, denoted by G _Δ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) denotes the maximum degree of G. A k -edge coloring of G is a function f : E(G) → L such that |L| = k and f (e ₁) ≠ f (e ₂) for all two adjacent edges e ₁ and e ₂ of G. The chromatic index of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G) = Δ(G) and Class 2 if χ′(G) = Δ(G) + 1. In this paper it is shown that every connected graph G of even order whose core is a cycle of order at most 13 is Class 1.     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

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.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On regular bipartite-preserving supergraphs

For a graphG with chromatic numberχ(G) ? 2 and maximum degree Δ(G), there exists anr-regular graphH, for everyr ? Δ(G), such thatG is an induced subgraph ofH and_χ(H) =_χ (G). In the case whereG is bipartite, the minimum order of such a graphH is determined.     

Total coloring of graphs embedded in surfaces of nonnegative Euler characteristic

Let G be a graph which can be embedded in a surface of nonnegative Euler characteristic.In this paper,it is proved that the total chromatic number of G is △(G)+1 if △(G)9,where △(G)is the maximum degree of G.     

Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs

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 (1) every oriented triangle-free planar graph has an oriented chromatic number at most 40, and (2) every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bounds of 47 and 67, respectively.     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

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.     

On the vertex face total chromatic number of planar graphs

Let G be a planar graph. The vertex face total chromatic number _χ13(G) of G is the least number of colors assigned to V(G)∪F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for all outerplanar graphs and modulus 3-regular maximal planar graphs. (2) We prove that if G is a maximal planar graph or a lower degree planar graph, i.e., ∠(G) ≤ 3, then _χ13(G) ≤ 6. © 1996 John Wiley & Sons, Inc.     

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.