Search

A connected ordering ( v 1 , v 2 , … , v n ) of V ( G ) is an ordering of the vertices such that v i has at least one neighbor in { v 1 , … , v i − 1 } for every i ∈ { 2 , … , n } . A connected greedy coloring (CGC for short) is a coloring obtained by applying the greedy algorithm to a connected ordering. This has been first introduced in 1989 by Hertz and de Werra, but still very little is known about this problem. An interesting aspect is that, contrary to the traditional greedy coloring, it is not always true that a graph has a connected ordering that produces an optimal coloring; this motivates the definition of the connected chromatic number of G , which is the smallest value χ c ( G ) such that there exists a CGC of G with χ c ( G ) colors. An even more interesting fact is that χ c ( G ) ≤ χ ( G ) + 1 for every graph G (Benevides et al. 2014). In this paper, in the light of the dichotomy for the coloring problem restricted to H -free graphs given by Kral’ et al. in 2001, we are interested in investigating the problems of, given an H -free graph G : (1). deciding whether χ c ( G ) = χ ( G ) ; and (2). given also a positive integer k , deciding whether χ c ( G ) ≤ k . We denote by P t the path on t vertices, and by P t + K 1 the union of P t and a single vertex. We have proved that Problem (2) has the same dichotomy as the coloring problem (namely, it is polynomial when H is an induced subgraph of P 4 or of P 3 + K 1 , and it is NP -complete otherwise). As for Problem (1), we have proved that χ c ( G ) = χ ( G ) always hold when H is an induced subgraph of P 5 or of P 4 + K 1 , and that it is NP -complete to decide whether χ c ( G ) = χ ( G ) when H is not a linear forest or contains an induced P 9 . We mention that some of the results involve fixed k and fixed χ ( G ) .

In this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for split graphs and several superclasses of cographs, extending a result of Havet and Zhu in 2013.

In this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for several superclasses of cographs, extending a result of Havet and Zhu in 2013.

In this paper, we study the achromatic and the pseudoachromatic numbers of planar and outerplanar graphs as well as planar graphs of girth 4 and graphs embedded on a surface. We give asymptotically tight results and lower bounds for maximal embedded graphs., 19 pages, 11 figures

Graph coloring is one of the fundamentally known NP-complete problem. Several heuristics have been developed to solve this problem, among which greedy coloring is the most naturally used one. In greedy coloring, vertices are traversed following an order and hence performance of it highly depends on finding a good order. In this paper, we propose an incremental search heuristic (ISH) which considers some ρ1 random orders and for each of them it calls a selective search (SS) procedure with parameter ρ2. Given an order, SS considers only those orders which produces equal or less number of distinct colors than a given order. We showed that those orders can be partitioned into disjoint subsets of equivalent orders. To make effective search, SS selects and evaluates only one order from such a subset. Analytically we have shown that ISH can solve the graph coloring instances on sparse graph in expected polynomial time. Through simulations, we have evaluated ISH on 86 challenging benchmarks and compare results with state of the art existing algorithms. We observed that ISH significantly outperforms existing algorithms specially for sparse graphs and also produces reasonably good results for others.

Post-print (lokagerð höfundar), We give a distributed (1+eps)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/eps) log* n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O(log* n) rounds were known. Linial's ring coloring lower bound implies that the dependency on log* n cannot be improved. We further prove that the dependency on 1/eps is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1+eps)-approximate multicoloring of directed trees in O((1/eps)log* n) rounds., Magnus M. Halldorsson is supported by grants 152679-05 and 174484-05 from the Icelandic Research Fund. Christian Konrad is supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1., "Peer Reviewed"

It is a common practice to find upper bound for clique number via legal coloring of the nodes of the graph. We will point out that with a little extra work we may lower this bound. Applying this procedure to a suitably constructed auxiliary graph one may further improve the clique size estimate of the original graph.

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with “enough” isolated vertices, Freckle Graphs. For Online Dominating Set , the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm. It is shown that it is NP -hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.

Given a graph G = ( V , E ) , a coloring function χ : V → C , assigning each vertex a color, is called convex if, for every color c ∈ C , the set of vertices with color c induces a connected subgraph of G . In the Convex Recoloring problem a colored graph G χ is given, and the goal is to find a convex coloring χ ′ of G that recolors a minimum number of vertices. In the weighted version each vertex has a weight, and the goal is to minimize the total weight of recolored vertices. The 2-Convex Recoloring problem ( 2 -CR) is the special case, where the given coloring χ assigns the same color to at most two vertices. 2 -CR is known to be NP-hard even if G is a path. We show that weighted 2 -CR cannot be approximated within any ratio, unless P = NP . On the other hand, we provide an alternative definition of (unweighted) 2 -CR in terms of maximum independent set of paths, which leads to a natural greedy algorithm. We prove that its approximation ratio is 3 2 and show that this analysis is tight. This is the first constant factor approximation algorithm for a variant of CR in general graphs. For the special case, where G is a path, the algorithm obtains a ratio of 5 4 , an improvement over the previous best known approximation. We also consider the problem of determining whether a given graph has a convex recoloring of size k . We use the above mentioned characterization of 2 -CR to show that a problem kernel of size 4 k can be obtained in linear time and to design an O ( | E | ) + 2 O ( k log k ) time algorithm for parameterized 2 -CR.

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.

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 .

Two vertex colorings of a graph G are equivalent if they induce the same partition of the vertex set into color classes. The graphical Bell number B ( G ) is the number of non-equivalent vertex colorings of G . We determine a sharp lower bound on B ( G ) for graphs G of order n and maximum degree n − 3 , and we characterize the graphs for which the bound is attained.

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.

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 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.

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 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.

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 .

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge-colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given r≥t≥2, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t−1 colors appear in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-colored stars with t edges. For large n, we show that, with the exception of the case t=2, the complete graph Kn is always the unique extremal graph. We also consider generalizations of this problem.

We analyse the size of an independent set in a random graph on $n$ vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as $n \to \infty$, expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges to the jamming constant as $n \to \infty$. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model., Comment: 25 pages

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.

Very recently, a long-standing open question proposed by Bodlaender in 1991 was answered: the graph coloring game is PSPACE-complete. In 2019, Andres and Lock proposed five variants of the graph coloring game and left open the question of PSPACE-hardness related to them. In this paper, we prove that these variants are PSPACE-complete for the graph coloring game and also for the greedy coloring game, even if the number of colors is the chromatic number. Finally, we also prove that a connected version of the graph coloring game, proposed by Charpentier et al. in 2019, is PSPACE-complete.

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 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.

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.

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.

Nilpotent adjacency matrix methods have proven useful for counting self-avoiding walks (paths, trails, cycles, and circuits) in finite graphs. In the current work, these methods are extended for the first time to problems related to graph colorings. Nilpotent-algebraic formulations of graph coloring problems include necessary and sufficient conditions for k-colorability, enumeration (counting) of heterogeneous and homogeneous paths, trails, cycles, and circuits in colored graphs, and a matrix-based greedy coloring algorithm. Introduced here also are the orthozeons and their application to counting monochromatic self-avoiding walks in colored graphs. The algebraic formalism easily lends itself to symbolic computations, and Mathematica-computed examples are presented throughout.

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 connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed ε>0 and integer n0≥1, there is a unit disk graph with bounded degree consisting of at least n0 vertices for which the output of the greedy algorithm is no better than 3−ε times of an optimum solution to the same graph.

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.

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 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.

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 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.

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 total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We construct infinite families of graphs for which the minimum number of colors to achieve the total chromatic sum is larger than the total chromatic number.