Search

For a nondecreasing sequence of integers S = (s 1 , s 2 , ...) an S-packing k-coloring of a graph G is a mapping from V(G) to { 1 , 2 , ... , k } such that vertices with color i have pairwise distance greater than s i . By setting s i = d + ⌊ i - 1 n ⌋ we obtain a (d, n)-packing coloring of a graph G. The smallest integer k for which there exists a (d, n)-packing coloring of G is called the (d, n)-packing chromatic number of G. In the special case when d and n are both equal to one we obtain the packing chromatic number of G. We determine the packing chromatic number of base-3 Sierpiński graphs and provide new results on (d, n)-packing chromatic colorings for this class of graphs. By using a dynamic algorithm, we establish the packing chromatic number for H-graphs. [ABSTRACT FROM AUTHOR]

A set S⊆V(G) is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G) of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v). The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d) of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2) for G=Cm□Cn□Ck, whenever k≥3 and (m,n)∈{(3,3),(3,4),(3,5),(4,4)} or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [ABSTRACT FROM AUTHOR]

A graphGis uniquelyk-colourable if the chromatic number ofGiskandGhas only onek-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg,One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graphGhas at most 4 triangles thenGhas two adjacent triangles. Furthermore, for any, we construct a uniquely 3-colourable planar graph withktriangles and without adjacent triangles. [ABSTRACT FROM PUBLISHER]

The frequency assignment problem asks for assigning frequencies to transmitters in a wireless network and includes a variety of specific subproblems. In particular, the packing coloring problem comes from the regulations concerning the assignment of broadcast frequencies to radio stations. The problem is placed on a graph-theoretical footing and modeled as the packing chromatic number χ ρ ( G ) of a graph G . The packing chromatic number of G is the smallest integer k such that the vertex set V ( G ) can be partitioned into disjoint classes X 1 , … , X k , with the condition that vertices in X i have pairwise distance greater than i . The determination of the packing chromatic number is known to be NP -hard. This paper presents an integer linear programming model and a satisfiability test model for the packing coloring problem. The proposed models were applied for studying the packing chromatic numbers of Cartesian products of paths and cycles and for the packing chromatic numbers of some distance graphs. [ABSTRACT FROM AUTHOR]

A local colouring of a graphGis a functionc: V(G)→ℕ such that for eachS⊆V(G), 2≤|S|≤3, there existu, v∈Swith |c(u)−c(v)| at least the number of edges in the subgraph induced byS. The maximum colour assigned bycis the value χℓ(c) ofc, and the local chromatic number ofGis χℓ(G)=min {χℓ(c):cis a local colouring ofG}. In this note the local chromatic number is determined for Cartesian productsG □ H, whereGandGHare 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that ifGandHare graphs such that χ(G)≤⌊ χℓ(H)/2 ⌋, then χℓ(G □ H)≤χℓ(H)+1. [ABSTRACT FROM AUTHOR]

Graph Coloring Problem, as one of the best known NP -complete problems, has been extensively studied by researchers in a wide range of fields, leading to many applications and theories in mathematics and computer science. In this paper, we focus on the design of exact algorithms for counting 3-colorings of a graph (denoted by #3- Coloring). Our approach is based on branch and reduce paradigm. We use the measure and conquer method to analyze the algorithms, in which we design two sets of measures (weights of vertices) intended for two distinct situations. In particular, we use the tree-width based technique to handle a special case by leveraging dynamic programming. As a result, we obtain an O (1. 58 8 n) -time algorithm for the #3- Coloring problem, which improves the previous O (1. 626 2 n) -time algorithm by Fomin et al. (2007). [ABSTRACT FROM AUTHOR]

Abstract: The square of a graph is obtained from by adding edges joining all pairs of nodes at distance 2 in . In this note we prove that for . This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327–2333]. [Copyright &y& Elsevier]

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G 4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G 4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G 4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G 4 . [ABSTRACT FROM AUTHOR]

A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k -coloring up to permutation of the colors. A uniquely k -colorable graph G is edge-critical if G − e is not a uniquely k -colorable graph for any edge e ∈ E ( G ) . Mel’nikov and Steinberg (Mel’nikov and Steinberg, 1977) asked to find an exact upper bound for the number of edges in an edge-critical uniquely 3-colorable planar graph with n vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if G is such a graph with n ( ≥ 6 ) vertices, then | E ( G ) | ≤ 5 2 n − 6 , which improves the upper bound 8 3 n − 17 3 given by Matsumoto (Matsumoto, 2013). Furthermore, we find some edge-critical uniquely 3-colorable planar graphs with n ( = 10 , 12 , 14 ) vertices and 5 2 n − 7 edges. [ABSTRACT FROM AUTHOR]