Equitable list coloring of planar graphs without 4- and 6-cycles

A graph G is equitably k-choosable if for any k-uniform list assignment L, there exists an L-colorable of G such that each color appears on at most vertices. Kostochka, Pelsmajer and West introduced this notion and conjectured that G is equitably k-choosable for k>Δ(G). We prove this for planar graphs with Δ(G)≥6 and no 4- or 6-cycles.     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

A result on the total colouring of powers of cycles

The total chromatic number χ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that for every simple graph G, χ_T(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.     

Spectral results on graphs with regularity constraints

Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k₁, τ₁)-regular set S₁ and a (k₂, τ₂)-regular set S₂ such that k₁ − τ₁ = k₂ − τ₂ = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, , induced by π, and the adjacency matrix of the quotient graph is obtained from the adjacency matrix of G/π.     

Covering line graphs with equivalence relations

An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3.     

Independence polynomials of k-tree related graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let α(G) denote the cardinality of a maximum independent set and f_s(G) for 0≤s≤α(G) denote the number of independent sets of s vertices. The independence polynomial defined first by Gutman and Harary has been the focus of considerable research recently. Wingard bounded the coefficients f_s(T) for trees T with n vertices: for s≥2. We generalize this result to bounds for a very large class of graphs, maximal k-degenerate graphs, a class which includes all k-trees. Additionally, we characterize all instances where our bounds are achieved, and determine exactly the independence polynomials of several classes of k-tree related graphs. Our main theorems generalize several related results known before.     

The incidence game chromatic number

We introduce the incidence game chromatic number which unifies the ideas of game chromatic number and incidence coloring number of an undirected graph. For k-degenerate graphs with maximum degree Δ, the upper bound 2Δ+4k−2 for the incidence game chromatic number is given. If Δ≥5k, we improve this bound to the value 2Δ+3k−1. We also determine the exact incidence game chromatic number of cycles, stars and sufficiently large wheels and obtain the lower bound for the incidence game chromatic number of graphs of maximum degree Δ.     

A connection between circular colorings and periodic schedules

We show that there is a curious connection between circular colorings of edge-weighted digraphs and periodic schedules of timed marked graphs. Circular coloring of an edge-weighted digraph was introduced by Mohar [B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107-116]. This kind of coloring is a very natural generalization of several well-known graph coloring problems including the usual circular coloring [X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371-410] and the circular coloring of vertex-weighted graphs [W. Deuber, X. Zhu, Circular coloring of weighted graphs, J. Graph Theory 23 (1996) 365-376]. Timed marked graphs [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAM J. Appl. Math. 14 (1966) 1390-1411] are used, in computer science, to model the data movement in parallel computations, where a vertex represents a task, an arc uv with weight c_uv represents a data channel with communication cost, and tokens on arc uv represent the input data of task vertex v. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if uv is an out-arc of u, then at time t+c_uv vertex u places one token on arc uv. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {f_u(1),f_u(2),f_u(3),…} such that vertex u starts its kth operation at time f_u(k) and each in-arc of u contains at least one token at that time. The set of functions is called a schedule of . Computer scientists are particularly interested in periodic schedules. Given a timed marked graph , they ask if there exist a period p>0 and real numbers x_u such that has a periodic schedule of the form f_u(k)=x_u+p(k−1) for each vertex u and any positive integer k. In this note we demonstrate an unexpected connection between circular colorings and periodic schedules. The aim of this note is to provide a possibility of translating problems and methods from one area of graph coloring to another area of computer science.     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

Coloring the Cartesian sum of graphs

For graphs G and H, let G⊕H denote their Cartesian sum. We investigate the chromatic number and the circular chromatic number for G⊕H. It has been proved that for any graphs G and H, . It has been conjectured that for any graphs G and H, . We confirm this conjecture for graphs G and H with special values of χ_c(G) and χ_c(H). These results improve previously known bounds on the corresponding coloring parameters for the Cartesian sum of graphs.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.