List circular coloring of trees and cycles

Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ? which assigns to each vertex v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.     

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     

On totally multicolored stars

Given an edge‐coloring of a graph G, a subgraph M of G will be called totally multicolored if no two edges of M receive the same color. Let h(G, K_1,q) be the minimum integer such that every edge‐coloring of G using exactly h(G, K_1,q) colors produces at least one totally multicolored copy of K_1,q (the q‐star) in G. In this article, an upper bound of h(G, K_1,q) is presented, as well as some applications of this upper bound. © 2005 Wiley Periodicals, Inc.     

On the pseudoachromatic index of the complete graph

Let q = 2^β be, for some β∈?, and let n = q² + q+ 1. By exhibiting a complete coloring of the edges of K_n, we show that the pseudoachromatic number ψ(G_n) of the complete line graph G_n = L(K_n)—or the pseudoachromatic index of K_n, if you will—is at least q³ + q. This bound improves the implicit bound of Jamison [Discrete Math 74 (1989), 99–115] which is given in terms of the achromatic number: ψ(G_n)≥α(G_n)≥q³ + 1. We also calculate, precisely, the pseudoachromatic number when q+ 1 extra points are added: Copyright © 2010 John Wiley Periodicals, Inc. J Graph Theory 66:89‐97, 2011     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Basic sets of Brauer characters of finite groups of Lie type,III

LetG(F ^q ) be a finite classical group whereq is odd and the centre ofG is connected. We show that there exists a set of irreducible characters ofG(F ^q ) such that the corresponding matrix of scalar products with the characters of Kawanaka’s generalized Gelfand-Graev representations is square unitriangular. This uses in an essential way Lusztig’s theory of character sheaves. As an application we prove that there exists an ordinary basic set of 2-modular Brauer characters and that the decomposition matrix of the principal 2-block ofG(F ^q ) has a lower unitriangular shape.     

Acyclic edge coloring of graphs with maximum degree 4

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 that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

Embedding finite graphs into graphs colored with infinitely many colors

We prove that for any cardinalτ and for any finite graphH there is a graphG such that for any coloring of the pairs of vertices ofG withτ colors there is always a copy ofH which is an induced subgraph ofG so that both the edges of the copy and the edges of the complement of the copy are monochromatic. Research supported by Hungarian National Science Foundation OTKA grant 1805.     

On <Emphasis Type="Italic">G</Emphasis>-invex multiobjective programming. Part II. Duality

This paper represents the second part of a study concerning the so-called G-multiobjective programming. A new approach to duality in differentiable vector optimization problems is presented. The techniques used are based on the results established in the paper: On G-invex multiobjective programming. Part I. Optimality by T.Antczak. In this work, we use a generalization of convexity, namely G-invexity, to prove new duality results for nonlinear differentiable multiobjective programming problems. For such vector optimization problems, a number of new vector duality problems is introduced. The so-called G-Mond–Weir, G-Wolfe and G-mixed dual vector problems to the primal one are defined. Furthermore, various so-called G-duality theorems are proved between the considered differentiable multiobjective programming problem and its nonconvex vector G-dual problems. Some previous duality results for differentiable multiobjective programming problems turn out to be special cases of the results described in the paper.     

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

A new upper bound for the harmonious chromatic number

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 257–261, 1998     

Maximal independent sets in minimum colorings

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].     

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     

A new approach to the linearity of testing planarity of graphs

In testing planarity of graphs, there are many criteria. The earliest one as known is the Kuratowski's theorem, then Whitney's, Maclane's, and so forth. Since the early sixties, people have begun researches on algorithms. Up to 1974, Hopcroft and Tarjan found an algorithm with a computing time being a linear function of the order of a graph. This is the linearity concerned here.This paper presents a new approach to the linearity by means of transforming the problem of testing planarity of a graphG into that of finding a spanning tree on another graphH, called an auxiliary graph ofG, with the order ofH being a linear function of that ofG. And moreover, we can also make the size ofH be a linear function of that ofG. The whole procedure is based on the building up of a theory of linear equations onGF (2) related toG.This was a report invited by RUTCOR, The State University of New Jersey, Rutgers, U. S. A. in 1984. And, the main part of this paper was completed during the author's stay at the Department of C & O, University of Waterloo, Canada.     

Finite groups in whichp′-classes haveq′-length

IfG is a finite group in which every element ofp′-order centralizes aq-Sylow subgroup ofG, wherep andq are distinct primes, it is shown thatO ^q′ (G) is solvable,l _q (G)≤1 andl _p (O ^q′ (G)) ≤2. Further, the structure ofG is determined to some extent. Work partially supported by MURST research program “Teoria dei gruppi ed applicazioni”.     

Multilevel least-change Newton-like methods for equality constrained optimization problems

This paper deals with the application of multilevel least-change Newton-like methods for solving twice continuously differentiable equality constrained optimization problems. We define multilevel partial-inverse least-change updates, multilevel least-change Newton-like methods without derivatives and multilevel projections of fragments of the matrix for Newton-like methods without derivatives. Local andq-superlinear convergence of these methods is proved. The theorems here also imply local andq-superlinear convergence of many standard Newton-like methods for nonconstrained and equality constraine optimization problems.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

An application of the regularity lemma in generalized Ramsey theory

Given graphs G and H, an edge coloring of G is called an (H,q)‐coloring if the edges of every copy of H ? G together receive at least q colors. Let r(G,H,q) denote the minimum number of colors in a (H,q)‐coloring of G. In 9 Erd?s and Gyárfás studied r(K_n,K_p,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by q_lin) for which r(K_n,K_p,q) is linear in n and the smallest q (denoted by q_quad) for which r(K_n,K_p,q) is quadratic in n. They raised the problem of determining the smallest q for which we have . In this paper by using the Regularity Lemma we show that if , then we have . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003