Search

A total coloring of a graph G is a functionsuch that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. A k-interval is a set of k consecutive integers. A cyclically interval total t-coloring of a graph G is a total coloring a of G with colors 1,2,...,t, such that at least one vertex or edge of G is colored by i,i=1,2,...,t, and for any, the set is a -interval, or is a -interval, where dG(x) is the degree of the vertex x in G. In this paper, we study the cyclically interval total colorings of cycles and middle graphs of cycles.

Given an undirected simple graph gg, an integer kk, and a cost cijcij for each pair of non-adjacent vertices in gg, a robust coloring of gg is the assignment of kk colors to vertices such that adjacent vertices get different colors and the total penalty of the pairs of vertices having the same color is minimum. The problem has applications in fields such as timetabling and scheduling. We present a new formulation for the problem, which extends an existing formulation for the graph coloring problem. We also discuss a column generation based solution method. We report computational study on the performance of alternative formulations and the column generation method.

International audience; In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost (2008), where given a graph GG, an auxiliary graph View the MathML sourceGˆ is constructed, such that the family of all stable sets of View the MathML sourceGˆ is in one-to-one correspondence with the family of all feasible colorings of GG. The transformation in Cornaz and Jost (2008) was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campêlo et al. (2008) and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances.

We demonstrate that for every positive integer $\Delta$, every K\_4-minor-free graph with maximum degree $\Delta$ admits an equitable coloring with k colors wherek $\ge$ ($\Delta$+3)/2. This bound is tight and confirms a conjecture by Zhang and Whu. We do not use the discharging method but rather exploit decomposition trees of K 4-minor-free graphs.

A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.

In this paper we study threshold-coloring of graphs, where the vertex colors represented by integers are used to describe any spanning subgraph of the given graph as follows. A pair of vertices with a small difference in their colors implies that the edge between them is present, while a pair of vertices with a big color difference implies that the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. Variants of the threshold-coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and describe a polynomial-time algorithm for another. (C) 2015 Elsevier B.V. All rights reserved.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the 'short code' of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on $n$-vertex hyper-graphs: * Coloring a 2-colorable 8-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log\log n})}}$ colors. * Coloring a 4-colorable 4-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log\log n})}}$ colors. * Coloring a 3-colorable 3-uniform hypergraph with $(\log n)^{\Omega(1/\log\log\log n)}$ colors. In each of these cases, the hardness results obtained are (at least) exponentially stronger than what was previously known for the respective cases. In fact, prior to this result, polylog n colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1)-colorable hypergraphs. The fundamental bottleneck in obtaining coloring inapproximability results using the low- degree long code was a multipartite structural restriction in the PCP construction of Dinur-Guruswami. We are able to get around this restriction by simulating the multipartite structure implicitly by querying just one partition (albeit requiring 8 queries), which yields our result for 2-colorable 8-uniform hypergraphs. The result for 4-colorable 4-uniform hypergraphs is obtained via a 'query doubling' method. For 3-colorable 3-uniform hypergraphs, we exploit the ternary domain to design a test with an additive (as opposed to multiplicative) noise function, and analyze its efficacy in killing high weight Fourier coefficients via the pseudorandom properties of an associated quadratic form., Comment: 25 pages

A proper incidentor coloring is called a (k, l)-coloring if the difference between the colors of the final and initial incidentors ranges between k and l. In the list variant, the extra restriction is added: the color of each incidentor must belong to the set of admissible colors of the arc. In order to make this restriction reasonable we assume that the set of admissible colors for each arc is an integer interval. The minimum length of the interval that guarantees the existence of a list incidentor (k, l)-coloring is called a list incidentor (k, l)-chromatic number. Some bounds for the list incidentor (k, l)-chromatic number are proved for multigraphs of degree 2 and 4.

We show two results related to the Hamiltonicity and $k$-Path algorithms in undirected graphs by Bj\"orklund [FOCS'10], and Bj\"orklund et al., [arXiv'10]. First, we demonstrate that the technique used can be generalized to finding some $k$-vertex tree with $l$ leaves in an $n$-vertex undirected graph in $O^*(1.657^k2^{l/2})$ time. It can be applied as a subroutine to solve the $k$-Internal Spanning Tree ($k$-IST) problem in $O^*(\min(3.455^k, 1.946^n))$ time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of $O^*(2^n)$. Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for $k$-Path and Hamiltonicity in any graph of maximum degree $\Delta=4,\ldots,12$ or with vector chromatic number at most 8.

A Grunbaum coloring of a triangulation G on a surface is a 3-edge coloring of G such that each face of G receives three distinct colors on its boundary edges. In this paper, we prove that every Fisk triangulation on the projective plane P has a Grunbaum coloring, where a "Fisk triangulation" is one with exactly two odd degree vertices such that the two odd vertices are adjacent. To prove the theorem, we establish a generating theorem for Fisk triangulations on P . Moreover, we show that a triangulation G on P has a Grunbaum coloring with each color-induced subgraph connected if and only if every vertex of G has even degree.

Indicated coloring is a graph coloring game in which there are two players jointly coloring the vertices of a graph in such a way that both can see the entire graph at all the time and in each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly without creating a monochromatic edge, using a fixed set of colors. The aim of Ann is to achieve a proper coloring for G, while Ben is trying to create a situation where all the colors occur on vertices adjacent to some uncolored vertex. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G, and is denoted by $$\chi _i(G)$$?i(G). In this paper, we obtain some upper bounds for the indicated chromatic number of graphs and find a smallest 3-regular graph for which the indicated chromatic number is 4. In addition, we introduce the concept of criticality of graphs with respect to the indicated chromatic number. Also we show that $$\{P_5,K_4-e\}$${P5,K4-e}-free graphs are k-indicated colorable for all $$k\ge \chi (G)$$k??(G).

Let G be a planar graph without 4-cycles and 5-cycles and with maximum degree Δi¾ź32. We prove that i¾źi¾źG2i¾źΔ+3. For arbitrarily large maximum degree Δ, there exist planar graphs GΔ of girth 6 with i¾źGΔ2=Δ+2. Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list-coloring. In addition, we prove bounds for Lp,q-labeling. Specifically, λ2,1Gi¾źΔ+8 and, more generally, λp,qGi¾ź2q-1Δ+6p-2q-2, for positive integers p and q with pi¾źq. Again, these bounds come from a greedy coloring, so they immediately extend to the list-coloring and online list-coloring variants of this problem.

A facial k -packing edge-coloring of a plane graph G is a coloring of its edges with colors 1 , … , k such that every facial trail containing two edges with the same color i has length at least i + 2 . The smallest integer k such that G admits a facial k -packing edge-coloring is denoted by p f ′ ( G ) . We prove that p f ′ ( G ) ≤ 20 for every 3-edge-connected plane graph G .

A graph H is immersed in a graph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. The notion of an immersion is quite similar to the well-known notion of a minor, as structural approach inspired by the theory of graph minors has been extremely successful in immersions.Hadwiger's conjecture on graph coloring, generalizing the Four Color Theorem, states that every loopless graph without a K k -minor is ( k - 1 ) -colorable, where K k is the complete graph on k vertices. This is a long standing open problem in graph theory, and it is even unknown whether it is possible to determine ck-colorability of K k -minor-free graphs in polynomial time for some constant c. In this paper, we address coloring graphs without H-immersion. In contrast to coloring H-minor-free graphs, we show the following:1.there exists a fixed-parameter algorithm to decide whether or not a given graph G without an immersion of a graph H of maximum degree d is ( d - 1 ) -colorable, where the size of H is a parameter. In fact, if G is ( d - 1 ) -colorable, the algorithm produces such a coloring, and2.for any positive integer k ( k ź 6 ), it is NP-complete to decide whether or not a given graph G without a K k -immersion is ( k - 3 ) -colorable.

Motivated by the Erdos-Faber-Lovász (EFL) conjecture for hypergraphs, we consider the edge coloring of linear hypergraphs. We discuss several conjectures for coloring linear hypergraphs that generalize both EFL and Vizing's theorem for graphs. For example, we conjecture that in a linear hypergraph of rank 3, the edge chromatic number is at most 2 times the maximum degree unless the hypergraph is the Fano plane where the number is 7. We show that for fixed rank sufficiently large and sufficiently large degree, the conjectures are true.

We consider list coloring of planar graphs without cycles of length in {4, …, 8}. List coloring is a generalization of the classical vertex coloring problem where each vertex has a list of colors associated with it. The goal is to proper vertex color the graph, such that each vertex gets a color available in its list. In this note, we prove that it is possible to 3-list color planar graphs without cycles of length in {4, …, 8} and with restrictions on 9-cycles.

Three edges e1, e2 and e3 in a graph G are consecutive if they form a path (in this order) or a cycle of length 3. The injective edge coloring number ź i ' ( G ) is the minimum number of colors permitted in a coloring of the edges of G such that if e1, e2 and e3 are consecutive edges in G, then e1 and e3 receive the different colors. Let ω' denote the number of edges in a maximum clique of G. A graph G is called an ω' edge injective colorable (or perfect EIC-)graph if ź i ' ( G ) = ω ' . In this paper, we give a sharp bound of the injective coloring number of a 2-connected graph with some forbidden conditions, and then we also characterize some perfect EIC-graph classes, which extends the results of perfect EIC-graph of Cardoso et al. in Injective edge chromatic index of a graph, http://arxiv.org/abs/1510.02626..

We propose two vertex-coloring problems for graphs, endorsing the spectrum of colors with a matrix of interferences between pairs of colors. In the Threshold Spectrum Coloring problem, the number of colors is fixed and the aim is to minimize the maximum interference at a vertex (interference threshold). In the Chromatic Spectrum Coloring problem, a threshold is settled and the aim is to minimize the number of colors (among the available ones) for which respecting that threshold is possible. We prove general upper bounds for the solutions to each problem, valid for any graph and any matrix of interferences. We also show that both problems are NP-hard and perform experimental results, proposing a DSATUR-based heuristic for each problem, in order to study the gap between the theoretical upper bounds and the values obtained., Ministerio de Economía y Competitividad, Comunidad de Madrid

A total coloring of a graph G is a coloring such that no two adjacent or incident elements receive the same color. In this field there is a famous conjecture, named Total Coloring Conjecture, saying that the the total chromatic number of each graph G is at most $$\Delta +2$$Δ+2. Let G be a planar graph with maximum degree $$\Delta \ge 7$$Δź7 and without adjacent chordal 6-cycles, that is, two cycles of length 6 with chord do not share common edges. In this paper, it is proved that the total chromatic number of G is $$\Delta +1$$Δ+1, which partly confirmed Total Coloring Conjecture.

Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used in a future paper of this series., Comment: 18 pages, 2 figures; v3: further reviewer remarks incorporated

Given a simple graph G = ( V , E ) and a function f from V to the positive integers, f is called a choice function of G if there is a proper vertex coloring ϕ such that ϕ ( v ) ∈ L ( v ) for all v ∈ V , where L ( v ) is any assignment of f ( v ) colors to v. The sum choice number χ s c ( G ) of G is defined to be the minimum of ∑ v ∈ V f ( v ) over all choice functions f of G. In this paper we provide several new lower bounds on χ s c ( G ) in terms of subgraphs of G.

A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. In this paper, we prove the tight bound of Behzad and Vizing conjecture on total coloring for Compound graph of G and H, where G and H are any graphs.

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on four vertices (not necessarily induced) is bi-colored. The star chromatic number of G is the minimum number of colors needed to star color G . In this note, we deduce upper bounds for the star chromatic number in terms of the clique number for some special classes of graphs which are defined by forbidden induced subgraphs.

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 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 obtain bounds for the b-chromatic number of powers of Q n , namely Q n p for all n ≥ 5 and ⌊ n 2 ⌋ p n − 1 . Also we obtain exact value of the b-chromatic number of Q p − n for all n ≥ 3 , and p = ⌊ n 2 ⌋ and p = n − 1 .

Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not "under control" from a polyhedral point of view. The equivalence between optimization and separation suggests the existence of integer programming formulations for these problems whose associated polytopes admit elegant characterizations. In this work we address this issue. As a starting point, we focus our attention on the well-known standard formulation for the classical vertex coloring problem. We present some general results about this formulation and we show that the vertex coloring polytope associated to this formulation for a graph G and a set of colors C corresponds to a face of the stable set polytope of a particular graph S G C . We further study the perfectness of S G C showing that when ź C ź 2 , this graph is perfect if and only if G is a block graph, from which we deduce a complete characterization of the associated coloring polytopes for block graphs. We also derive a new family of valid inequalities generalizing several known families from the literature and we conjecture that this family is sufficient to completely describe the vertex coloring polytope associated to cacti graphs.

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge choice functions f of G.

Given a graph G , its k -coloring graph is the graph whose vertex set is the proper k -colorings of the vertices of G with two k -colorings adjacent if they differ at exactly one vertex. In this paper, we consider the question: Which graphs can be coloring graphs? In other words, given a graph H , do there exist G and k such that H is the k -coloring graph of G ? We will answer this question for several classes of graphs and discuss important obstructions to being a coloring graph involving order, girth, and induced subgraphs.

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is also called total coloring. We consider a planar graph G with maximum degree Δ(G) ≥ 8, and proved that if G contains no adjacent i, j-cycles with two chords for some i, j ∈ {5, 6, 7}, then G is total-(Δ + 1)-colorable.

Given a weighted undirected graph? G and a nonnegative integer? k , the maximum? k -star colorable subgraph problem consists of finding an induced subgraph of? G which has maximum weight and can be star colored with at most? k colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. In this article, we investigate the polyhedral properties of this problem. In particular, we characterize cases in which the inequalities that appear in a natural integer programming formulation define facets. Moreover, we identify graph classes for which these base inequalities give a complete linear description. We then study path graphs in more detail and provide a complete linear description for an alternative polytope for? k = 2 . Finally, we derive complete balanced bipartite subgraph inequalities and present some computational results.

A (closed) neighborhood-restricted ? 2 -coloring of a graph G is an assignment of colors to the vertices of G such that no more than two colors are assigned in any closed neighborhood, that is, for every vertex v in G , the vertex v and its neighbors are in at most two different color classes. The ? 2 -achromatic number is defined as the maximum number of colors in any ? 2 -coloring of G . We study the ? 2 -achromatic number. In particular, we improve a known upper bound and characterize the extremal graphs for some other known bounds.

The known fact that coloring of the nodes of a graph improves the performance of practical clique search algorithm is the main motivation of this paper. We will describe a number of ways in which an edge coloring scheme proposed in [8] can be used in clique search. The edge coloring provides an upper bound for the clique number. This estimate has a limitation. It will be shown that the gap between the clique number and the upper bound can be arbitrarily large. Finally, it will be shown that to determine the optimal number of colors in an edge coloring is NP-hard.

Graph coloring theory has a wide range of applications in many scientific fields. As an application, graph distinguishing colorings may be connected with the frequency assignment problem in wireless communication. The vertices (nodes) of graphs (networks) represent transmitters, the set C u , f of colors assigned to a vertex u and the edges (links) incident to u under a total coloring f indicates the frequencies usable. One constrain C u , f ? C v , f ensures the corresponding two stations u, v can operate on a wide range of frequencies without the danger of interfering with each other. We propose new total colorings having more constraints for researching deeply the frequency assignment problem. Under a proper total coloring f of a simple graph G, f ( u ) and f ( u v ) are the color assigned to a vertex u and the color assigned to an edge uv, respectively. We use C ( f , u ) to denote the set of colors assigned to the edges incident to u, C { f , u } the union of f ( u ) and the set of colors assigned to the neighbors of u, so we have other two color sets C f , u = C ( f , u ) ? { f ( u ) } , and C 2 f , u = C ( f , u ) ? C { f , u } . We say f an adjacent vertex distinguishing total coloring (AVDTC) of G if one constraint C f , u ? C f , v holds for each edge uv of G, and the minimum number of k colors required for which G admits an AVDTC is denoted as ? a s ? ( G ) , which is related with a conjecture: ? a s ? ( G ) ? Δ ( G ) + 3 , where Δ ( G ) is the maximum degree. We call f a 4-adjacent vertex distinguishing total coloring (4-AVDTC) of G if four distinguishing constraints C ( f , x ) ? C ( f , y ) , C { f , x } ? C { f , y } , C f , x ? C f , y and C 2 f , x ? C 2 f , y hold simultaneously true for every edge uv of G, and the least number of k colors required for which G admits a k-4-AVDTC is denoted by ? 4 a s ? ( G ) . We conjecture ? 4 a s ? ( G ) ? Δ ( G ) + 4 if any edge uv of G holds that the set of neighbors of the vertex u differs from the set of neighbors of the vertex v. A proper edge-coloring of a simple graph G is called a vertex distinguishing edge-coloring if for any two distinct vertices u and v of G, the set of the colors assigned to the edges incident to u differs from the set of the colors assigned to the edges incident to v. We extend such distinguishing edge colorings to proper total colorings with many distinguishing constraints and color several kinds of graphs totally with the least number of colors such that the graphs admit proper total colorings having at least four distinguishing constraints.

A strong edge coloring of a graph G is a proper edge coloring in which no two edges of the same color lie within distance 2 from each other. The minimum number of colors required for strong edge coloring of a graph G is called strong chromatic index and is denoted by $$\chi _{s}^{\prime } (G)$$źsź(G). Channel assignment problems are closely related with strong edge coloring problem where the colors represent frequencies. In wireless networks, assigning channels or frequencies to the links between transceivers (vertices) to avoid interference can be modelled as a strong edge coloring problem. In this paper, we determine the exact values of strong chromatic indices of interconnection networks namely butterfly network, Benes network, hypertree network and honeycomb network.

A classic result of Thue states that using 3 symbols one can construct an infinite nonrepetitive sequence, that is, a sequence without two identical adjacent blocks. In this paper, we present Thue-type results concerning coloring of the Euclidean plane, related to the famous Hadwiger-Nelson problem. This old problem asks for the chromatic number of the unit distance graph of the plane, the infinite graph with the set of vertices of R 2 and edges between points at distance 1 .We solve a problem posed by Grytczuk (2008) by showing that any coloring of the unit distance graph of R 2 in which the sequence of colors of every simple path is nonrepetitive needs more than countable number of colors. Grytczuk, Kosinski and Zmarz (2016) introduced a relaxation of this problem, by restricting the?nonrepetitiveness condition to a certain class of paths. Let a path in the unit distance graph of R 2 be called line path if it consists of collinear points. A coloring of R 2 is line nonrepetitive if the sequence of colors on every line path is nonrepetitive. We present a line nonrepetitive 18 -coloring of R 2 , which improves the result of Grytczuk, Kosinski and Zmarz with 36 colors. Furthermore, we construct a line nonrepetitive coloring, which additionally avoids palindromes and uses 32 colors.We also consider a natural generalization of this problem to other patterns. We say that a pattern q (finite sequence over a set of variables E ) occurs in a sequence w (over an alphabet A ) if there exists a?substitution f from E to the set of nonempty sequences over A such that f ( q ) is a block in w . A sequence w avoids a?pattern q if q does not occur in w . For a pattern q , a coloring of R 2 is called line p -free if the sequence of colors on every line path avoids q . We present a 9 -coloring of R 2 which is line α α α -free and line α β α β -free at once. Moreover, we give a non-constructive result for a class of patterns. Namely, let q be a pattern with no variable occurring exactly once or satisfying ? ? 2 d , where ? is the length of q and d is the number of variables in q . Then there exists a line q -free coloring of R 2 using a finite number of colors. In fact, this result holds even if (instead of taking into account only line paths) we consider all sequences of points in R 2 with consecutive distances in some fixed interval a , b and without any pair of vertices at distance smaller than a fixed e 0 .

A proper vertex k -coloring of a graph G is dynamic if for every vertex v with degree at least 2, the neighbors of v receive at least two different colors. The smallest integer k such that G has a dynamic k -coloring is the dynamic chromatic number ? d ( G ) . In this paper the differences between ? d ( G ) and ? d ( G - e ) , and between ? d ( G ) and ? d ( G - v ) are investigated respectively.

Given a graph together with a partition of its vertex set, the minimum selective coloring problem consists of selecting one vertex per partition set such that the chromatic number of the subgraph induced by the selected vertices is minimum. The contribution of this paper is twofold. First, we investigate the complexity status of the minimum selective coloring problem in some specific graph classes motivated by some models described in Demange et al. (2015). Second, we introduce a new problem that corresponds to the worst situation in the minimum selective coloring; the maximum selective coloring problem aims to select one vertex per partition set such that the chromatic number of the subgraph induced by the selected vertices is maximum. We motivate this problem by different models and give some first results concerning its complexity. (C) 2015 Elsevier B.V. All rights reserved.

Let G be a graph with chromatic number χ ( G ) and consider a partition P of G into connected subgraphs. P is a puzzle on G if there is a unique vertex coloring of G using 1, 2, …, χ ( G ) such that the sums of the numbers assigned to the partition pieces are all the same. P is an apuzzle if there is a unique vertex coloring such that the sums are all different. We investigate the concept of puzzling and apuzzling graphs, detailing classes of graphs that are puzzling, apuzzling and neither.

We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.

An r -dynamic k -coloring of a graph G is a proper vertex k -coloring of G such that the neighbors of any vertex v receive at least min { r , deg ( v ) } different colors. The r -dynamic chromatic number of G , ? r ( G ) , is defined as the smallest k such that G admits an r -dynamic k -coloring. In this paper, first we introduce an upper bound for ? r ( G ) in terms of r , chromatic number, maximum degree and minimum degree. Then, motivated by a conjecture of Montgomery (2001) stating that for a d -regular graph G , ? 2 ( G ) - ? ( G ) ? 2 , we prove two upper bounds for ? 2 - ? on regular graphs. Our first upper bound ? 5.437 log d + 2.721 ? improves a result of Alishahi (2011). Also, our second upper bound shows that Montgomery's conjecture is implied by the existence of a ? ( G ) -coloring for any regular graph G , such that any two vertices whose neighbors are unicolored in this coloring, have no common neighbor.

A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.

In this paper we propose a hybrid Ant Colony Optimization (ACO) algorithm for the Partition Graph Coloring Problem (PGCP). Given an undirected graph G = ( V , E ) , whose nodes are partitioned into a given number of the sets, the goal of the PGCP is to find a subset V ? ? V that contains exactly one node from each cluster and a coloring for V ? so that in the graph induced by V ? , two adjacent nodes have different colors and the total number of used colors is minimal. Our hybrid algorithm is obtained by executing a local search procedure after every ACO iteration. The performance of our algorithm is evaluated on a set of instances commonly used as benchmark and the computational results show that compared to state-of-the-art algorithms, our improved hybrid ACO algorithm achieves solid results in very short run-times.

Let G = ( V , E ) be a simple graph with vertex set V and edge set E. Define an integer-valued function f on V such that f(v) > 0 for every v ∈ V. An f-coloring of G is an edge-coloring of it such that each color class appears at every vertex v ∈ V(G) at most f(v) times. In this paper, we give a sufficient condition for a simple graph with large maximum degree to be of f-class 1.

The pseudoachromatic index of the finite affine space $\mathrm{AG}(n,q),$ denoted by $\psi'(\mathrm{AG}(n,q)),$ is the the maximum number of colors in any complete line-coloring of $\mathrm{AG}(n,q).$ When the coloring is also proper, the maximum number of colors is called the achromatic index of $\mathrm{AG}(n,q).$ We prove that if $n$ is even then $\psi'(\mathrm{AG}(n,q))\sim q^{1.5n-1}$; while when $n$ is odd the value is bounded by $q^{1.5(n-1)}, Comment: 21 pages

By the Road Coloring Theorem (Trahtman, 2008), the edges of any aperiodic directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted. For certain words it is NP-complete to decide whether there is a suitable coloring of a given multigraph. We present a classification of all words over the binary alphabet that separates such words from those that make the problem solvable in polynomial time. We show that the classification becomes different if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete., Comment: To be presented at LATA 2015