Plane graphs of maximum degree Δ ≥ 7 are edge-face (Δ + 1)-colorable

A plane graph G is edge-face k-colorable if its edges and faces can be colored with k colors such that any two adjacent or incident elements receive different colors. It is known that every plane graph G of maximum degree Δ ≥ 8 is edge-face (Δ + 1)-colorable. The condition Δ ≥ 8 is improved to Δ ≥ 7 in this paper.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Isomorphic factorizations of trees

A tree is even if its edges can be colored in two colors so that the monochromatic subgraphs are isomorphic. All even trees of maximum degree 3 in which no two vertices of degrees 1 or 3 are adjacent are determined. It is also shown that, for every n, there are only finitely many trees of maximum degree 3 and with n vertices of degree 3 that are not even. © 1995 John Wiley & Sons, Inc.     

On the chromatic spectrum of acyclic decompositions of graphs

If G is any graph, a G‐decomposition of a host graph H = (V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G‐decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G‐spectrum of H is the set of all chromatic indices taken on by G‐decompositions of H. If both S and T are trees, then the S‐spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S‐spectrum has two values, and if the host is allowed to be arbitrary, the S‐spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S‐spectrum of a general bipartite graph is NP‐hard. We show that if G has c > 1 components, then there is a host H whose G‐spectrum contains both 3 and 2c + 1. If G is a forest, then there is a tree T whose G‐spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007     

Maximal antiramsey graphs and the strong chromatic number

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X_s(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, ?) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well-studied (but little understood) functions r_k(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k-term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

Plane Graphs with Maximum Degree 6 are Edge-face 8-colorable

A plane graph G is edge-face k-colorable if the elements of \({E(G) \cup F(G)}\) can be colored with k colors so that any two adjacent or incident elements receive different colors. Sanders and Zhao conjectured that every plane graph with maximum degree Δ is edge-face (Δ +  2)-colorable and left the cases \({\Delta \in \{4, 5, 6\}}\) unsolved. In this paper, we settle the case Δ =  6. More precisely, we prove that every plane graph with maximum degree 6 is edge-face 8-colorable.     

Colorful monochromatic connectivity

An edge-coloring of a connected graph is monochromatically-connecting if there is a monochromatic path joining any two vertices. How “colorful” can a monochromatically-connecting coloring be? Let mc(G) denote the maximum number of colors used in a monochromatically-connecting coloring of a graph G. We prove some nontrivial upper and lower bounds for mc(G) and relate it to other graph parameters such as the chromatic number, the connectivity, the maximum degree, and the diameter.     

Polychromatic colorings of bounded degree plane graphs

A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K₄ or a subdivision of K₄ on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009     

Special monochromatic trees in two-colored complete graphs

For a positive integer k, a set of k + 1 vertices in a graph is a k-cluster if the difference between degrees of any two of its vertices is at most k − 1. Given any tree T with at least k³ edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of T such that some vertices in the copy form a k-cluster in G. The same conclusion holds for any tree T having a vertex of degree more than k. © 1997 John Wiley & Sons, Inc.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Improved upper bounds on acyclic edge colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors.The acyclic chromatic index of a graph G,denoted by a′(G),is the minimum number k such that there is an acyclic edge coloring using k colors.It is known that a′(G)≤16△for every graph G where △denotes the maximum degree of G.We prove that a′(G)13.8△for an arbitrary graph G.We also reduce the upper bounds of a′(G)to 9.8△and 9△with girth 5 and 7,respectively.     

Chromatically Supremal Decompositions of Graphs

If G is a graph, a G-decomposition of a host graph H is a partition of the edges of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition of H is the minimum number of colors required to color the parts of the decomposition so that parts which share a common node get different colors. We establish an upper bound on the chromatic index and characterize those decompositions which achieve it. The structurally most interesting of the decompositions with maximal chromatic index are associated with (v, k, 1)-designs.     

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.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

On smallest regular graphs with a given isopart

For a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphs H having a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a connected regular graph H having a decomposition into t subgraphs isomorphic to G. In this article, the values of these parameters are determined for complete graphs, cycles, and stars. Furthermore, we show that Δ(T) ? r(T) ? δ (T) + 1 for every tree T. and r(T) Δ(T) if the maximum degree Δ(T) is even.     

Monochromatic Kr‐Decompositions of Graphs

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let be the smallest number ? such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H‐decomposition with at most ? parts. Here, we study the function for and .     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997