Search

A graph is locally-connected if the neighborhood of each vertex induces a connected graph. It is well known that a triangulation on a closed surface is locally-connected, and some results for triangulations were generalized to those for connected locally-connected graphs. In this paper, we extend two characterization theorems of triangulations for a complete coloring and a facial complete coloring, which are vertex colorings with constraints on the appearance of color tuples, to those of connected locally-connected graphs. Moreover, we also investigate the relation between the corresponding invariants and the number of independent elements.

International audience; In this paper, we generalize the concept of complete coloring and achromatic number to 2-edge-colored graphs and signed graphs. We give some useful relationships between different possible definitions of such achromatic numbers and prove that computing any of them is NP-complete.

In 1967 Harary, Hedetniemi, and Prins showed that every graph G admits a complete t-coloring for every t with χ ( G ) ≤ t ≤ ψ ( G ) , where χ ( G ) denotes the chromatic number of G and ψ ( G ) denotes the achromatic number of G which is the maximum number r for which G admits a complete r-coloring. Recently, Edwards and Rzazewski (2020) showed that this result fails for hypergraphs by proving that for every integer k with k ≥ 9 , there exists a k-uniform hypergraph H with a complete χ ( H ) -coloring and a complete ψ ( H ) -coloring, but no complete t-coloring for some t with χ ( H ) t ψ ( H ) . They also asked whether there would exist such an example for 3-uniform hypergraphs and posed another problem to strengthen their result. In this paper, we generalize their result to all cases k with k ≥ 3 and settle their problems by giving several examples of 3-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and Ohno (2020) who suggested a special family of 3-uniform hypergraph to satisfy the desired interpolation property.

Let G be a graph embedded in a surface of nonnegative characteristic with maximum degree $$\varDelta $$ . The entire chromatic number $$\chi _\mathrm{vef}$$ of G is the least number of colors such that any two adjacent or incident elements in $$V(G)\cup E(G) \cup F(G)$$ have different colors. In this paper, we prove that $$\chi _\mathrm{vef}(G)\le \varDelta +4$$ if $$\varDelta \ge 6$$ , and $$\chi _\mathrm{vef}(G)\le \varDelta +5$$ if $$\varDelta \le 5$$ .

The packing chromatic number $$\chi _{\rho }(G)$$ of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets $$V_i$$ , $$i\in \{1,\ldots ,k\}$$ , where each $$V_i$$ is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpinski-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpinski graphs with base 3, we prove that it is unbounded in the families of Sierpinski graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpinski triangle graphs $$ST^n_3$$ is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpinski graphs $$S^n_G$$ with respect to all connected graphs G of order 4.

A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching. The strong chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. Let $\Delta \geq 4$ be an integer. In this note, we study the odd graphs and show the existence of some special walks. By using these results and Chang's ideas in [Discuss. Math. Graph Theory 34 (4) (2014) 723--733], we show that every planar graph with maximum degree at most $\Delta$ and girth at least $10 \Delta - 4$ has a strong edge coloring with $2\Delta - 1$ colors. In addition, we prove that if $G$ is a graph with girth at least $2\Delta - 1$ and mad$(G) < 2 + \frac{1}{3\Delta - 2}$, where $\Delta$ is the maximum degree and $\Delta \geq 4$, then $\chi_s'(G) \leq 2\Delta - 1$, if $G$ is a subcubic graph with girth at least $8$ and mad$(G) < 2 + \frac{2}{23}$, then $\chi_s'(G) \leq 5$., Comment: 7 pages

A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if they are adjacent to a common edge or share an endpoint. The strong chromatic index of a graph G, denoted by χ s ′ ( G ) , is the minimum number of colors needed for a strong edge coloring of G. We determine the strong chromatic index of the generalized Petersen graphs P(n, k) when 1 ≤ k ≤ 3.

The maximum k-colorable subgraph problem (k-MCSP) is to color as many vertices as possible with at most k colors, such that no two adjacent vertices share the same color. We consider online algorithms for this NP -hard problem, and give bounds on their competitive ratio. We then consider a large family A of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in A can produce an optimal solution to the k-MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored.

In the paper, we show that the incidence chromatic number χi of a complete k-partite graph is at most Δ + 2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to Δ + 1 if and only if the smallest part has only one vertex (i.e., Δ = n − 1). Formally, for a complete k-partite graph G = Kr1,r2,...,rk with the size of the smallest part equal to r1 ≥ 1 we have χi(G)={Δ(G)+1if r1=1,Δ(G)+2if r1>1.$$\chi _i (G) = \left\{ {\matrix{{\Delta (G) + 1} & {{\rm{if}}\;r_1 = 1,} \cr {\Delta (G) + 2} & {{\rm{if}}\;r_1 > 1.} \cr } } \right.$$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is 𝒩𝒫-complete, thus we prove also the 𝒩𝒫-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is 𝒩𝒫-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).

The on-line interval coloring and its variants are important combinatorial problems with many applications in network multiplexing, resource allocation and job scheduling. In this paper we present a new lower bound of 4.1626 for the asymptotic competitive ratio for the on-line coloring of intervals with bandwidth which improves the best known lower bound of 24 7 . For the on-line coloring of unit intervals with bandwidth we improve the lower bound of 1.831 to 2.

A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the set of colors used on vertices of the closed neighborhoods of u and v are distinct. The lid-chromatic number is the minimum number of colors used in a lid-coloring. In this paper we prove a relation between lid-coloring and a variation, called strong lid-coloring. With this, we obtain linear time algorithms to calculate the lid-chromatic number for some classes of graphs with few P 4 's, such as cographs, P 4 -sparse graphs and ( q , q − 4 ) -graphs. We also prove that the lid-chromatic number is O ( n 1 − e ) -inapproximable in polynomial time for every e > 0 , unless P = NP .

In this paper, we introduce a new coloring of graphs called ( N , p ) -equitable b-coloring. An ( N , p ) -equitable b-coloring of a graph G is a proper vertex coloring with N colors such that each color class contains at least one vertex adjacent to every other used color, with the constraint that any two color classes differ in size by at most p , with p ≥ 0 . The aim of this new coloring is to seek an ( N , p ) -equitable b-coloring of G which simultaneously maximizes the number of color classes and minimizes the maximum size difference between any two color classes. Here we show that this coloring can be represented by a bi-objective problem that maximizes N and minimizes p . We define the equitable b-chromatic number of G , denoted by χ e b ( G ) , as the largest integer k for which G has an ( N , p ) -equitable b-coloring with k = N − p . We present three variants which correspond to the possible cases that we can encounter when solving the problem and we examine and analyze them separately. Furthermore, we prove that the problem of determining the ( N , p ) -equitable b-coloring of a graph G with N colors is N P -complete. Moreover, we obtain some lower bounds and exact values for trees and we distinguish some particular cases when a pivoted tree or an arbitrary not pivoted tree can be ( N , p ) -equitable b-colorable with p = 0 or p = 1 . Finally, we summarize, draw conclusions and point out some directions for future work.

The minimum sum coloring problem ( M S C P ) is a vertex coloring problem in which a weight is associated with each color. Its aim is to find a coloring of the vertices of a graph G with the minimum sum of the weights of the used colors. The M S C P has important applications in the fields such as scheduling and VLSI design. The minimum number of colors among all optimal solutions of the M S C P for G is called the chromatic strength of G and is denoted by s ( G ) . A tight upper bound of s ( G ) allows to significantly reduce the search space when solving the M S C P . In this paper, we propose and empirically evaluate two new upper bounds of s ( G ) for general graphs, U B A and U B S , based on an abstraction of all possible colorings of G formulated as an ordered set of decreasing positive integer sequences. The experimental results on the standard benchmarks DIMACS and COLOR show that U B A is competitive, and that U B S is significantly tighter than those previously proposed in the literature for 70 graphs out of 74 and, in particular, reaches optimality for 8 graphs. Moreover, both U B A and U B S can be applied to the more general optimum cost chromatic partition ( O C C P ) problem.

Given a simple graph G , a proper total- k -coloring ϕ : V ( G ) ∪ E ( G ) → { 1 , 2 , … , k } is called neighbor sum distinguishing if S ϕ ( u ) ≠ S ϕ ( v ) for any two adjacent vertices u, v ∈ V ( G ), where S ϕ ( u ) is the sum of the color of u and the colors of the edges incident with u . It has been conjectured by Pilśniak and Woźniak that Δ ( G ) + 3 colors enable the existence of a neighbor sum distinguishing total coloring. The conjecture is confirmed for any graph with maximum degree at most 3 and for planar graph with maximum degree at least 11. We prove that the conjecture holds for any planar graph G with Δ ( G ) = 10 . Moreover, for any planar graph G with Δ( G ) ≥ 11, Δ ( G ) + 2 colors guarantee such a total coloring, and the upper bound Δ ( G ) + 2 is tight.

A harmonious coloring of a k -uniform hypergraph H is a rainbow vertex coloring such that each k -set of colors appears on at most one edge. A rainbow coloring of H is achromatic if each k -set of colors appears on at least one edge. The harmonious number (resp. achromatic number) of H , denoted by h ( H ) (resp. ψ ( H ) ) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H . A class H of hypergraphs is fragmentable if for every H ∈ H , H can be fragmented into components of a bounded size by removing a “small” fraction of vertices. We show that for every fragmentable class H of bounded degree hypergraphs, for every ϵ > 0 and for every hypergraph H ∈ H with m ≥ m 0 ( H , ϵ ) edges we have h ( H ) ≤ ( 1 + ϵ ) k ! m k and ψ ( H ) ≥ ( 1 − ϵ ) k ! m k . As corollaries, we answer a question posed by Blackburn concerning the maximum length of t -subset packing sequences of constant radius and derive an asymptotically tight bound on the minimum number of colors in a vertex-distinguishing edge coloring of cubic planar graphs, which is a step towards confirming a conjecture of Burris and Schelp.

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that for any pair of adjacent vertices, the set of colors appearing on the vertex and incident edges are different. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ a ′ ′ ( G ) . Let G be a graph, and χ ( G ) and χ ′ ( G ) be the chromatic number and edge chromatic number of G , respectively. In this paper we show that χ a ′ ′ ( G ) ≤ χ ( G ) + χ ′ ( G ) − 1 for any graph G with χ ( G ) ≥ 6 , and χ a ′ ′ ( G ) ≤ χ ( G ) + Δ ( G ) for any graph G . Our results improve the only known upper bound 2 Δ obtained by Huang et al. (2012). As a direct consequence, we have χ a ′ ′ ( G ) ≤ Δ ( G ) + 3 if χ ( G ) = 3 and thus it implies the known results on graphs with maximum degree 3, K 4 -minor-free graphs, outerplanar graphs, graphs with maximum average degree less than 3, planar graphs with girth at least 4 and 2-degenerate graphs.

A proper edge coloring f of a graph G with colors 1 , 2 , 3 , … , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G , the colors on the edges incident to v either form an interval or the set { 1 , … , t } ∖ { f ( e ) : e is incident to v } is an interval. A bipartite graph G is ( a , b ) -biregular if every vertex in one part has degree a and every vertex in the other part has degree b ; it has been conjectured that all such graphs have interval colorings. We prove that every ( 3 , 5 ) -biregular graph has a cyclic interval coloring and we give several sufficient conditions for a ( 3 , 5 ) -biregular graph to admit an interval coloring.

In a proper edge coloring of a graph, the set of colors of a vertex v is the set of colors of the edges incident to v, C(v). If C ( u ) ≠ C ( v ) for every adjacent vertices u and v, this edge coloring is an AVD-edge coloring. The least number of colors for which G has an AVD-edge coloring is called the AVD-chromatic index, χ a ′ ( G ) . We determine the AVD-chromatic index for the powers of paths.

In this survey the following types of colorings of plane graphs are discussed, both in their vertex and edge versions: facially proper coloring, rainbow coloring, antirainbow coloring, loose coloring, polychromatic coloring, l -facial coloring, nonrepetitive coloring, odd coloring, unique-maximum coloring, WORM coloring, ranking coloring and packing coloring. In the last section of this paper we show that using the language of words these different types of colorings can be formulated in a more general unified setting.

A coloring of the vertices of a connected graph is r-convex if each color class induces a subgraph with at most r components. We address the r-convex recoloring problem defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G so that the resulting coloring is r-convex. This problem, known to be NP -hard even on paths, was first investigated on trees and for r = 1 , motivated by applications on perfect phylogenies. The concept of r-convexity, for r ≥ 2 , was proposed later, and it is also of interest in the study of protein-protein interaction networks and phylogenetic networks. Here, we show that, for each r ∈ N , the r-convex recoloring problem on n-vertex bipartite graphs cannot be approximated within a factor of n 1 − e for any e > 0 , unless P = NP . We also provide strong hardness results for weighted and parametrized versions of the problem.

This paper investigates the vertex coloring problem in an uncertain graph in which all vertices are deterministic, while all edges are not deterministic and exist with some degree of belief in uncertain measures. The concept of the maximal uncertain independent vertex set of an uncertain graph is first introduced. We then present a degree of belief rule to obtain the family of maximal uncertain independent vertex sets. Based on the maximal uncertain independent vertex set, some properties of the separation degree of an uncertain graph are discussed. Following that, the concept of an uncertain chromatic set is introduced. Then, a maximum separation degree algorithm is derived to obtain the uncertain chromatic set. Finally, numerical examples are presented to demonstrate the application of the vertex coloring problem in uncertain graphs and the effectiveness of the maximum separation degree algorithm.

A sequence r 1 , r 2 , … , r 2 n is called an anagram if r n + 1 , r n + 2 , … , r 2 n is a permutation of r 1 , r 2 , … , r n . A sequence S is called anagram-free if no block (i.e. subsequence of consecutive terms of S ) is an anagram. A coloring of the edges of a given plane graph G is called facial anagram-free if the sequence of colors on any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) in G is anagram-free. In this paper we show that every connected plane graph G admits a facial anagram-free edge-coloring with at most 11 colors. Moreover, if G is a 3 -connected plane graph, then 9 colors suffice for such a coloring.

Coupon coloring is a new coloring which has many applications. A k -coupon coloring of a graph G is a k -coloring of G by colors [ k ] = { 1 , 2 , … , k } such that the neighborhood of every vertex of G contains vertices of all colors from [ k ]. The maximum integer k for which a k -coupon coloring exists is called the coupon coloring number of G , and it is denoted by χ c ( G ). In this paper, we studied the coupon coloring of cographs, which are graphs that can be generated from the single vertex graph K 1 by complementation and disjoint union, and have applications in many interesting problems. We use the cotree representation of a cograph to give a polynomial time algorithm to color the vertices of a cograph, and then prove that this coloring is a coupon coloring with maximum colors, hence get the coupon coloring numbers of the cograph.

We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space; the constant bases of the exponentials are significantly smaller than in previous works. For example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with $d$ colors in time within a polynomial factor of O(2^{(d-1)n/2}). Our techniques build upon and generalize some recently published ideas by I. Koutis (ICALP 2009), R. Williams (IPL 2009), and A. Bj\"orklund (STACS 2010, FOCS 2010).

The chromatic number of a graph is bounded below by its clique number and from above by its maximum degree plus one. In 1998, Reed conjectured that the chromatic number is at most halfway in between these trivial lower and upper bounds. Moreover, Reed proved that its at most some non-trivial convex combination of the two bounds. In 2012, King and Reed produced a short proof that, provided the maximum degree is large enough, a combination of 1/130,000 suffices. Recently Bonamy, Perrett, and the second author improved this to 1/26. It is natural to wonder if similar results hold for the list chromatic number. Unfortunately, previous techniques for ordinary coloring do not extend to list coloring. In this paper, we overcome these hurdles by introducing several new ideas. Our main result is that the list chromatic number is at most some non-trivial convex combination of the clique number and the maximum degree plus one. Furthermore, we show that for large enough maximum degree, that a combination of 1/13 suffices. Note that this also improves on the best known results for ordinary coloring.

We say that a coloring of R 2 is line k-nonrepetitive if we will never encounter the same sequence of colors k times in a row when going along any straight line with steps of length 1 unit. This notion is closely related to square- and cube-free words, introduced by Thue. We show that there exists a line 40-nonrepetitive coloring of the plane with only 2 colors. Moreover, we generalize this result for higher dimensions and more general patterns. It complements recent results concerning line 2-nonrepetitive colorings of the plane.

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we have obtained bounds for the b-chromatic number of powers of Qn, namely Qnp, for n5 and n2

Feder and Subi conjectured that for any 2 -coloring of the edges of the n -dimensional cube, there is an antipodal pair of vertices connected by a path that changes color at most once. They proved that if the coloring is such that there are no properly edge colored 4 -cycles, the conjecture is true, without a color change. We generalize their theorem by weakening the assumption on the coloring. Our method can be applied to a similar question on any graph, if the condition on the coloring is satisfied. We solve the corresponding problem on the toroidal grid of size 2 a × 2 b .

A vertex coloring is said to be 2-distance if any two distinct vertices of distance at most 2 receive different colors. Let G be a planar graph with girth at least 5. In this paper, we prove that G admits a 2-distance coloring with at most $$\Delta (G)+3$$ colors if $$\Delta (G)\ge 339$$ .

It is known that Total Coloring Conjecture (TCC) was verified for planar graphs with maximum degree 6. In this paper, we prove that TCC holds for planar graphs G with (G)=6, if G does not contain any subgraph isomorphic to a 4-fan.

A proper edge coloring is called acyclic if no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree $$\varDelta $$ is acyclically edge- $$(\varDelta +2)$$ -colorable. Basavaraju and Chandran (J Graph Theory 61:192–209, 2009) confirmed the conjecture for non-regular graphs G with $$\varDelta =4$$ . In this paper, we extend this result by showing that every 4-regular graph G without 3-cycles is acyclically edge-6-colorable.

Given a graph G, the anti-Ramsey number $$AR(K_n,G)$$ is defined to be the maximum number of colors in an edge-coloring of $$K_n$$ which does not contain any rainbow G (i.e., all the edges of G have distinct colors). The anti-Ramsey number was introduced by Erdős et al. (Infinite and finite sets, pp 657–665, 1973) and so far it has been determined for several special graph classes. Another related interesting problem posed by Erdős et al. is the uniqueness of the extremal coloring for the anti-Ramsey number. Contrary to the anti-Ramsey number, there are few results about the extremal coloring. In this paper, we show the uniqueness of such extremal coloring for the anti-Ramsey number of matchings in the complete graph.

An equitable graph coloring is a proper vertex coloring of a graph G where the sizes of the color classes differ by at most one. The equitable chromatic number, denoted by $$\chi _{eq}(G),$$ is the smallest number k such that G admits such equitable k-coloring. We focus on enumerative algorithms for the computation of $$\chi _{eq}(G)$$ and propose a general scheme to derive pruning rules for them: We show how the extendability of a partial coloring into an equitable coloring can be modeled via network flows. Thus, we obtain pruning rules which can be checked via flow algorithms. Computational experiments show that the search tree of enumerative algorithms can be significantly reduced in size by these rules and, in most instances, such naive approach even yields a faster algorithm. Moreover, the stability, i.e., the number of solved instances within a given time limit, is greatly improved. Since the execution of flow algorithms at each node of a search tree is time consuming, we derive arithmetic pruning rules (generalized Hall-conditions) from the network model. Adding these rules to an enumerative algorithm yields an even larger runtime improvement.

We show that the chromatic number of { P 5 , K p − e } -free graphs can be computed in polynomial time for each fixed p . Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for { P 5 , P 3 + P 2 ¯ } -free graphs.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using Õ ( n 4/11 ) colors. This is the first combinatorial improvement since Blum’s Õ ( n 3/8 ) bound from FOCS’90. Like Blum’s algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for the polynomial time algorithm for the coloring of 3-colorable graphs from O ( n 0.2072 ) colors by Chlamtac from FOCS’07 to O ( n 0.2049 ) colors. Next, we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to O ( n 0.19996 ) colors.

Let k be a positive integer. An adjacent vertex distinguishing (for short, AVD) total k -coloring ϕ of a graph G is a proper total k -coloring of G such that no pair of adjacent vertices have the same set of colors, where the set of colors at a vertex v is { ϕ ( v ) } ∪ { ϕ ( e ) : e is incident to v } . Zhang et al. conjectured in 2005 that every graph with maximum degree Δ has an AVD total ( Δ + 3 ) -coloring. Recently, Papaioannou and Raftopoulou confirmed the conjecture for 4 -regular graphs. In this paper, by applying the Combinatorial Nullstellensatz, we verify the conjecture for all graphs with maximum degree 4.

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over tilde(upsilon) of each vertex upsilon, the number of vertices in (N) over tilde(upsilon) boolean AND V-i is (at most) a given integer h(upsilon)(i). The complexity of some variations is discussed according to (N) over tilde(upsilon), which may be the usual neighbors, or the vertices at distance at most 2, or the closed neighborhood of upsilon (upsilon and its neighbors). Polynomially solvable cases are exhibited (in particular when G is a special tree). (C) 2009 Elsevier B.V. All rights reserved.

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].

A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a graph G has a biclique (resp. star) edge-coloring using two colors is NP-hard. Furthermore, we describe polynomial time algorithms for the problem in restricted classes: K3-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles. Fil: Dantas, Simone. Universidade Federal Fluminense; Brasil Fil: Groshaus, Marina Esther. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Guedes, André. Universidade Federal do Paraná; Brasil Fil: Machado, Raphael C. S.. Instituto Nacional de Metrologia, Qualidade e Tecnologia ; Brasil Fil: Ries, Bernard. University of Fribourg; Suiza Fil: Sasaki, Diana. Universidade Federal do Rio de Janeiro; Brasil

A proper edge-k-coloring of a graph G is a mapping from E(G) to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different fromthe sumof colors taken on the edges incident to v. Let χ′Σ(G) denote the smallest value k in such a coloring of G. This parameter makes sense for graphs containing no isolated edges (we call such graphs normal). The maximum average degree mad(G) of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad(G) < 5/2, then χ′Σ(G) ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.

In this paper we study a problem of vertex two-coloring of an undirected graph such that there is no monochromatic cycle of the given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from the variation of satisfiability (SAT) problem. We show the nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction.