Neighbor sum distinguishing list total coloring of subcubic graphs

Let \(G=(V, E)\) be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by \(\mathrm{ch}_{\Sigma }^{t}(G)\), is the smallest integer k such that, after assigning each \(z\in V\cup E\) a set L(z) of k real numbers, G has a total coloring \(\phi \) satisfying \(\phi (z)\in L(z)\) for each \(z\in V\cup E\) and \(\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)\) for each \(uv\in E\). In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that \(\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3\) for every subcubic graph G.     

New bounds for locally irregular chromatic index of bipartite and subcubic graphs

A graph is locally irregular if the neighbors of every vertex v have degrees distinct from the degree of v. A locally irregular edge-coloring of a graph G is an (improper) edge-coloring such that the graph induced on the edges of any color class is locally irregular. It is conjectured that three colors suffice for a locally irregular edge-coloring. In the paper, we develop a method using which we prove four colors are enough for a locally irregular edge-coloring of any subcubic graph admiting such a coloring. We believe that our method can be further extended to prove the tight bound of three colors for such graphs. Furthermore, using a combination of existing results, we present an improvement of the bounds for bipartite graphs and general graphs, setting the best upper bounds to 7 and 220, respectively.     

Note on incidence chromatic number of subquartic graphs

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.     

Independent domination in subcubic graphs

Journal of Combinatorial Optimization - A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent...     

Neighbor-sum-distinguishing edge choosability of subcubic graphs

A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\) denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7\); (2) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6\) if \(\hbox {mad}(G)<\frac{36}{13}\); (3) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5\) if \(\hbox {mad}(G)<\frac{5}{2}\).     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

A combinatorial proof for the circular chromatic number of Kneser graphs

Chen (J Combin Theory A 118(3):1062–1071, 2011) confirmed the Johnson–Holroyd–Stahl conjecture that the circular chromatic number of a Kneser graph is equal to its chromatic number. A shorter proof of this result was given by Chang et al. (J Combin Theory A 120:159–163, 2013). Both proofs were based on Fan’s lemma (Ann Math 56:431–437, 1952) in algebraic topology. In this article we give a further simplified proof of this result. Moreover, by specializing a constructive proof of Fan’s lemma by Prescott and Su (J Combin Theory A 111:257–265, 2005), our proof is self-contained and combinatorial.     

Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles

Let $\chi'_{a}(G)$ and Δ(G) denote the acyclic chromatic index and the maximum degree of a graph G, respectively. Fiam?ík conjectured that $\chi'_{a}(G)\leq \varDelta (G)+2$ . Even for planar graphs, this conjecture remains open with large gap. Let G be a planar graph without 4-cycles. Fiedorowicz et al. showed that $\chi'_{a}(G)\leq \varDelta (G)+15$ . Recently Hou et al. improved the upper bound to Δ(G)+4. In this paper, we further improve the upper bound to Δ(G)+3.     

Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

Gyárfás conjectured that for a given forest F, there exists an integer function f(F, x) such that \(\chi (G)\le f(F,\omega (G))\) for each F-free graph G, where \(\omega (G)\) is the clique number of G. The broom B(m, n) is the tree of order \(m+n\) obtained from identifying a vertex of degree 1 of the path \(P_m\) with the center of the star \(K_{1,n}\). In this note, we prove that every connected, triangle-free and B(m, n)-free graph is \((m+n-2)\)-colorable as an extension of a result of Randerath and Schiermeyer and a result of Gyárfás, Szemeredi and Tuza. In addition, it is also shown that every connected, triangle-free, \(C_4\)-free and T-free graph is \((p-2)\)-colorable, where T is a tree of order \(p\ge 4\) and \(T\not \cong K_{1,3}\).     

List edge and list total coloring of planar graphs with maximum degree 8

Let \(G\) be a planar graph with maximum degree \(\varDelta \ge 8\) and without chordal 5-cycles. Then \(\chi '_{l}(G)=\varDelta \) and \(\chi ''_{l}(G)=\varDelta +1\).     

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

A note on the minimum number of choosability of planar graphs

The problem of minimum number of choosability of graphs was first introduced by Vizing. It appears in some practical problems when concerning frequency assignment. In this paper, we study two important list coloring, list edge coloring and list total coloring. We prove that \(\chi '_{l}(G)=\varDelta \) and \(\chi ''_{l}(G)=\varDelta +1\) for planar graphs with \(\varDelta \ge 8\) and without adjacent 4-cycles.     

The adjacent vertex distinguishing total chromatic numbers of planar graphs with $$\Delta =10$$

A (proper) total-k-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\mapsto \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge \(uv\in E(G)\), \(C(u)\ne C(v)\). We denote the smallest value k in such a coloring of G by \(\chi ''_{a}(G)\). It is known that \(\chi _{a}''(G)\le \Delta (G)+3\) for any planar graph with \(\Delta (G)\ge 11\). In this paper, we show that if G is a planar graph with \(\Delta (G)\ge 10\), then \(\chi _{a}''(G)\le \Delta (G)+3\). Our approach is based on Combinatorial Nullstellensatz and the discharging method.     

Minimum choosability of planar graphs

The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring \(\phi \) such that \(\phi (x) \in L(x)\). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring \(\phi \) such that \(\phi (x) \in L(x)\). We proved \(\chi '_{l}(G)=\Delta \) and \(\chi ''_{l}(G)=\Delta +1\) for a planar graph G with maximum degree \(\Delta \ge 8\) and without chordal 6-cycles, where the list edge chromatic number \(\chi '_{l}(G)\) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number \(\chi ''_{l}(G)\) of G is the smallest integer k such that G is total-k-choosable.     

Acyclically 3-colorable planar graphs

In this paper we study the acyclic 3-colorability of some subclasses of planar graphs. First, we show that there exist infinite classes of cubic planar graphs that are not acyclically 3-colorable. Then, we show that every planar graph has a subdivision with one vertex per edge that is acyclically 3-colorable and provide a linear-time coloring algorithm. Finally, we characterize the series-parallel graphs for which every 3-coloring is acyclic and provide a linear-time recognition algorithm for such graphs.     

On list <Emphasis Type="Italic">r</Emphasis>-hued coloring of planar graphs

A list assignment of G is a function L that assigns to each vertex \(v\in V(G)\) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring \(\phi \) such that for any vertex v with degree d(v), \(\phi (v)\in L(v)\) and v is adjacent to at least \( min\{d(v),r\}\) different colors. The list r-hued chromatic number of G, \(\chi _{L,r}(G)\), is the least integer k such that for every list assignment L with \(|L(v)|=k\), \(v\in V(G)\), G has an (L, r)-coloring. We show that if \(r\ge 32\) and G is a planar graph without 4-cycles, then \(\chi _{L,r}(G)\le r+8\). This result implies that for a planar graph with maximum degree \(\varDelta \ge 26\) and without 4-cycles, Wagner’s conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds.     

An optimal square coloring of planar graphs

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.