Search

Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-and-conquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-of-the-art graph coloring methods.

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

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.

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.

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.

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.

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.

In 2004, Karonski, ?uczak and Thomason posed the conjecture that every graph admits a vertex-coloring edge 3-weighting using colors 1, 2, 3. In this paper, we prove that this conjecture is true if the vertex-coloring is relaxed to be a tree-coloring. Furthermore, we verify that some classes of graphs permit tree-coloring edge 2-weightings.

We show that depth first search can be used to give a proper coloring of connected signed graphs G using at most $$\Delta (G)$$ colors, provided G is different from a balanced complete graph, a balanced cycle of odd length, and an unbalanced cycle of even length, thus giving a new, short proof to the generalization of Brooks’ theorem to signed graphs, first proved by Macajova, Raspaud, and Skoviera.

Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277–288] that G admits an acyclic coloring with O(Δ4/3) colors and a proper coloring with O(Δ(k-1)/(k-2)) colors such that no path with k vertices is bichromatic for a fixed integer k ≥ 5. In this paper, we combine above two colorings and show that if k ≥ 5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ(k-1)/(k-2)) colors such that no path with k vertices is bichromatic.

Let G be a graph without isolated vertices. A k-coupon coloring of G is a k-coloring of G such that the neighborhood of every vertex of G contains vertices of all colors from $$[k] =\{1, 2, \ldots , k\}$$[k]={1,2,ź,k}, which was recently introduced by Chen, Kim, Tait and Verstraete. The coupon coloring number$$\chi _c(G)$$źc(G) of G is the maximum k for which a k-coupon coloring exists. In this paper, we mainly study the coupon coloring of some special classes of graphs. We determine the coupon coloring numbers of complete graphs, complete k-partite graphs, wheels, cycles, unicyclic graphs, bicyclic graphs and generalised $$\Theta $$ź-graphs.

After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.

The First-Fit (or Grundy) chromatic number of a graph G denoted by $$\chi _{{_\mathsf{FF}}}(G)$$źFF(G), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number $$\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1$$źźFF(G)/2ź+1. Using this result we prove that for every $$t\ge 2$$tź2 there exists a real number $$c>0$$c>0 such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most $$cn^{1/t}$$cn1/t colors. It is noted that for $$t=2$$t=2 this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.

A vertex coloring is called $$2$$2-distance if any two vertices at distance at most $$2$$2 from each other get different colors. The minimum number of colors in 2-distance colorings of $$G$$G is its 2-distance chromatic number, denoted by $$\chi _2(G)$$ź2(G). Let $$G$$G be a plane graph with girth at least $$5$$5. In this paper, we prove that $$\chi _2(G)\le \Delta +8$$ź2(G)≤Δ+8 for arbitrary $$\Delta (G)$$Δ(G), which partially improves some known results.

Let $$G=(V,E)$$G=(V,E) be a simple graph and for every vertex $$v\in V$$v?V let $$L(v)$$L(v) be a set (list) of available colors. The graph $$G$$G is called $$L$$L-colorable if there is a proper coloring $$\varphi $$? of the vertices with $$\varphi (v)\in L(v)$$?(v)?L(v) for all $$v\in V$$v?V. A function $$f:V(G) \rightarrow \mathbb N$$f:V(G)?N is called a choice function of $$G$$G and $$G$$G is said to be $$f$$f-list colorable if $$G$$G is $$L$$L-colorable for every list assignment $$L$$L with $$|L(v)|=f(v)$$|L(v)|=f(v) for all $$v\in V$$v?V. Set $${{\mathrm{size}}}(f)=\sum \nolimits _{v\in V} f(v)$$size(f)=?v?Vf(v) and define the sum choice number$$\chi _{sc}(G)$$?sc(G) as the minimum of $${{\mathrm{size}}}(f)$$size(f) over all choice functions $$f$$f of $$G$$G. It is easy to see that $$\chi _{sc}(G)\le |V|+|E|$$?sc(G)≤|V|+|E| for every graph $$G$$G and that there is a greedy coloring of $$G$$G for the corresponding choice function $$f$$f and every list assignment with $$|L(v)|=f(v)$$|L(v)|=f(v). Therefore, a graph $$G$$G with $$\chi _{sc}(G)=|V|+|E|$$?sc(G)=|V|+|E| is called $$sc$$sc-greedy. The concept of the sum choice number was introduced in 2002 by Isaak. In 2006, Heinold characterized the broken wheels (or fan graphs) with respect to $$sc$$sc-greedyness and obtained some results for wheels. In this paper we extend the result for wheels and provide a complete characterization of wheels concerning this property.

A vertex coloring of a graph $$G$$G is called acyclic if it is a proper vertex coloring such that every cycle $$C$$C receives at least three colors. The acyclic chromatic number of $$G$$G is the least number of colors in an acyclic coloring of $$G$$G. We prove that acyclic chromatic number of any graph $$G$$G with maximum degree $$\Delta \ge 4$$Δ?4 and with girth at least $$4\Delta $$4Δ is at most $$12\Delta $$12Δ.

Millimeter wave (mmWave) communications is one of the key technologies for future 5th generation (5G) wireless networks. In this paper, we investigate the problem of medium access control (MAC) in mmWave networks. We develop a frame-based scheduling directional MAC protocol, termed FDMAC, to achieve the goal of leveraging collision-free concurrent transmissions to fully exploit spatial reuse in mmWave networks. The high efficiency of FDMAC is achieved by amortizing the scheduling overhead over multiple concurrent, back-to-back transmissions in a row. The core of FDMAC is a graph coloring-based scheduling algorithm, termed greedy coloring (GC) algorithm, that can compute near-optimal schedules with respect to the total transmission time with low complexity. FDMAC is analyzed and evaluated with simulations.

Indicated coloring is a graph coloring game in which there are two players collectively coloring the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph $$G$$G, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $$G$$G (regardless of Ben's strategy) is called the indicated chromatic number of $$G$$G, and is denoted by $$\chi _i(G)$$?i(G). In this paper, we have shown that cographs, chordal graphs, complement of bipartite graphs, $$\{P_5,K_3\}$${P5,K3}-free graphs and $$\{P_5, \mathrm{paw}\}$${P5,paw}-free graphs are $$k$$k-indicated colorable for all $$k\ge \chi _i(G)$$k??i(G). This provides a partial answer to a question raised in Grzesik (Discret Math 312:3467---3472, 2012). Also we have discussed the Brooks' type result for indicated coloring.

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes.

This paper presents a novel compiler algorithm, called acyclic orientation graph coloring (AOG coloring), for managing data objects in software-managed memory allocation. The key insight is that softwaremanaged memory allocation could be solved as an interval coloring problem, or equivalently, an acyclic orientation problem. We generalize graph coloring register allocation to interval coloring memory allocation by maintaining an acyclic orientation to the currently colored subgraph. This is achieved with some well-crafted heuristics, including Aggressive Simplify that does not necessarily preserve colorability and Best-Fit Select that assigns intervals (i.e., colors) to nodes by possibly adjusting the colors already assigned to other nodes earlier. Our algorithm generalizes and subsumes as a special case the classical graph coloring register allocation algorithm without notably increased complexity: it deals with memory allocation while preserving the elegance and practicality of traditional graph coloring register allocation. We have implemented our algorithm and tested it on Appel’s 27921 interference graphs for scalars (augmented with node weights). Our algorithm outperforms Memory Coloring, the best in the literature, for software-managed memory allocation, on 98.64% graphs, in which, the gaps are more than 20% on 68.31% graphs and worse only on 0.29% graphs. We also tested it on all the 73 DIMACS weighted benchmarks (weighted graphs), AOG Coloring outperforms Memory Coloring on all of the benchmarks, in which, the gaps are more than 20% on 83.56% graphs.

This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.

Finding large cliques in a graph is an important problem in applied discrete mathematics. In directed graph a possible corresponding problem is finding large transitive subtournaments. It is well-known that coloring the graph speeds up the clique search in the undirected case. In this paper we propose coloring schemes to speed up the tournament search in the directed case. We prove two complexity results about the proposed colorings. A consequence of these results is that in practical computations we have to be content with approximate greedy coloring algorithms.

Circular coloring is a popular branch of graph theory which has been exhaustively studied for two decades mainly from a theoretical perspective. Since it is a refinement of the traditional proper coloring, it provides a more accurate model for cyclic scheduling problems which often arise in industrial applications. The present paper briefly surveys a special class of open shop scheduling that can be solved via circular coloring, and then proposes a new mathematical programming model and tabu search algorithm to compute the circular chromatic number of a graph effectively.

For every graph G, the coloring number of G does not exceed the least strong limit cardinal above the graph’s list-chromatic number.

A proper coloring in which all colors have equal numbers of vertices is called a uniform proper coloring of a graph New condition for the existence of uniform coloring are proved.

We consider a proper coloring c of edges and vertices in a simple graph and the sum f(v) of colors of all the edges incident to v and the color of a vertex v. We say that a coloring c distinguishes adjacent vertices by sums, if every two adjacent vertices have different values of f. We conjecture that $${\Delta +\,3}$$ Δ + 3 colors suffice to distinguish adjacent vertices in any simple graph. In this paper we show that this holds for complete graphs, cycles, bipartite graphs, cubic graphs and graphs with maximum degree at most three.

Algorithmica, 70 (1), ISSN:0178-4617, ISSN:1432-0541

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.

Greedy embedding is a graph embedding that makes the simple greedy geometric packet forwarding successful for every source-destination pair. It is desirable that graph embeddings also yield low hop overhead (stretch) of the greedy paths over the corresponding shortest paths. In this paper we study how topological and geometric properties of embedded graphs influence the hop stretch. Based on the obtained insights, we design embedding heuristics that yield minimal hop stretch greedy embeddings and verify their effectiveness on models of synthetic graphs. Finally, we verify the effectiveness of our heuristics on instances of several classes of large, real-world network graphs.

Wireless sensor networks should provide with valuable service, which is called service-oriented requirement. To meet this need, a novel distributed graph coloring based time division multiple access scheduling algorithm (GCSA), considering real-time performance for clustering-based sensor network, is proposed in this paper, to determine the smallest length of conflict-free assignment of timeslots for intra-cluster transmissions. GCSA involves two phases. In coloring phase, networks are modeled using graph theory, and a distributed vertex coloring algorithm, which is a distance-2 coloring algorithm and can get colors near to $$(\updelta +1)$$ , is proposed to assign a color to each node in the network. Then, in scheduling phase, each independent set is mapped to a unique timeslot according to the set's priority which is obtained by considering network structure. The experimental results indicate that GCSA can significantly decrease intra-cluster delay and increase intra-cluster throughput, which satisfies real-time performance as well as communication reliability.

The best method known for determining lower bounds on the vertex coloring number of a graph is the linear-programming column-generation technique, where variables correspond to stable sets, first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numerically-safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price framework for graph coloring. Computational results are presented on a collection of standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989.

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least $${\lceil\frac{r}{2}\rceil}$$ different {K 2, C i | i ? 3}-factors.

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v ,w hereuv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χAa(G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.

In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two.

The square coloring of a graph is to color the vertices of a graph at distance at most 2 with different colors. In 1977, Wegner posed a conjecture on square coloring of planar graphs. The conjecture is still open. In this paper, we prove that Wegner's conjecture is true for planar graphs with girth at least 6.

In this work we investigate a new graph coloring constructive hyper-heuristic for solving examination timetabling problems. We utilize the hierarchical hybridizations of four low level graph coloring heuristics, these being largest degree, saturation degree, largest colored degree and largest enrollment. These are hybridized to produce four ordered lists. For each list, the difficulty index of scheduling the first exam is calculated by considering its order in all lists to obtain a combined evaluation of its difficulty. The most difficult exam to be scheduled is scheduled first (i.e. the one with the minimum difficulty index). To improve the effectiveness of timeslot selection, a roulette wheel selection mechanism is included in the algorithm to probabilistically select an appropriate timeslot for the chosen exam. We test our proposed approach on the most widely used un-capacitated Carter benchmarks and also on the recently introduced examination timetable dataset from the 2007 International Timetabling Competition. Compared against other methodologies, our results demonstrate that the graph coloring constructive hyper-heuristic produces good results and outperforms other approaches on some of the benchmark instances.

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted χgd(G). It is known that there exist graphs such that χg0(G) = 3, but χg1(G) > 3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m ≤ χg0(G) < χg1(G).

International audience; A dominator coloring is a coloring of the vertices of a graph such that every vertex is either alone in its color class or adjacent to all vertices of at least one other class. We present new bounds on the dominator coloring number of a graph, with applications to chordal graphs. We show how to compute the dominator coloring number in polynomial time for P4-free graphs, and we give a polynomial-time characterization of graphs with dominator coloring number at most 3.

Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, (g, f)-coloring and equitable edge-coloring of graphs are introduced. In particular, some new results related to the above colorings obtained by the authors are given. Some new problems and conjectures are presented.

Generalizing the idea of the Lovasz extension of a set function and the discrete Choquet integral, we introduce a combinatorial model that allows us to define and analyze matroid-type greedy algorithms. The model is based on a real-valued function v on a (finite) family of sets which yields the constraints of a combinatorial linear program. Moreover, v gives rise to a ranking and selection procedure for the elements of the ground set N and thus implies a greedy algorithm for the linear program. It is proved that the greedy algorithm is guaranteed to produce primal and dual optimal solutions if and only if an associated functional on $${\mathbb{R}^N}$$ is concave. Previous matroid-type greedy models are shown to fit into the present general context. In particular, a general model for combinatorial optimization under supermodular constraints is presented which guarantees the greedy algorithm to work.

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemeredi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn 2) time, where n is the number of vertices.

Given a graph G=(V,E) with strictly positive integer weights ? i on the vertices i?V, an interval coloring of G is a function I that assigns an interval I(i) of ? i consecutive integers (called colors) to each vertex i?V so that I(i)?I(j)=? for all edges {i,j}?E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight ? ij is associated with each edge {i,j}?E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i?V so that |c(i)?c(j)|?? ij for all edges {i,j}?E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.

This paper investigates ways of applying oscillator synchronization to graph coloring. A previous method based on the generalization of the Aihara model is sensitive to the varying degree of the vertices in the graph and there is a strong tendency for the network to form suboptimal limit cycles on regular graphs. Other models such as those by Wu and Nakaguchi, Jin’no and Tanaka do not generalize well into greater than 2-coloring. In this paper, we present ways to overcome these problems and describe the results of our experiments on graphs requiring more than two colors. Our k-phase model enhances the coloring performance over the previous similar models. We further attempt to formalize and analyze the categorical behavior of these systems and discuss connections to other optimization methods.

We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio of 4−3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195–199, 2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring algorithms.

Coloring a k-colorable graph using k colors (k≥3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the uniform distribution over k-colorable graphs with n vertices and exactly cn edges, c greater than some sufficiently large constant. We rigorously show that all proper k-colorings of most such graphs lie in a single “cluster”, and agree on all but a small, though constant, portion of the vertices. We also describe a polynomial time algorithm that whp finds a proper k-coloring of such a random k-colorable graph, thus asserting that most such graphs are easy to color. This should be contrasted with the setting of very sparse random graphs (which are k-colorable whp), where experimental results show some regime of edge density to be difficult for many coloring heuristics.

Coloring of the graph products, especially vertex and edge coloring, has been widely researched for all types of graph products. For total graph coloring, as combination of edge and vertex coloring, Behzad and Vizing set Total Coloring Conjecture in mid 1960s. In this paper, we prove the conjecture for two specific direct graph products, for direct product of path and arbitrary graph G, Pn×G, where χ′(G)=Δ(G), and expand the proof onto direct product of arbitrary cycle and a path Pn, Cm×Pn. At the same time, the proofs provide the algorithms to color such graphs.

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G.