List star edge coloring of k-degenerate graphs

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree $\Delta$ is at most $?\frac{3\Delta }{2}?$, which is tight. In this paper, we study the list star edge coloring of $k$-degenerate graphs. Let $c{h}_{st}^{\prime }\left(G\right)$ be the list star chromatic index of $G$: the minimum $s$ such that for every $s$-list assignment $L$ for the edges, $G$ has a star edge coloring from $L$. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. $c{h}_{st}^{\prime }\left(T\right)\le ?\frac{3\Delta }{2}?$ for any tree $T$ with maximum degree $\Delta$. And then by applying some orientation technique we present two upper bounds for list star chromatic index of $k$-degenerate graphs.     

The odd-valued chromatic polynomial of a signed graph

For a signed graph $\mathrm{\Sigma }=(G,\sigma )$, Zaslavsky defined a proper coloring on Σ and showed that the function counting the number of such colorings is a quasi-polynomial with period two, that is, a pair of polynomials, one for odd values and the other for even values. In this paper, we focus on the case of odd, written as $\chi (\mathrm{\Sigma },x)$ for short. We initially give a homomorphism expression of such colorings, by which the symmetry is considered in counting the number of homomorphisms. Besides, the explicit formulas $\chi (\mathrm{\Sigma },x)$ for some basic classes of signed graphs are presented. As a main result, we give a combinatorial interpretation of the coefficients in $\chi (\mathrm{\Sigma },x)$ and present several applications. In particular, the constant term in $\chi (\mathrm{\Sigma },x)$ gives a new criterion for balancing and a characterization for unbalanced unicyclic graph. At last, we also give a tight bound for the constant term of $\chi (\mathrm{\Sigma },x)$.     

Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 9

Let $k$ be a positive integer. An adjacent vertex distinguishing (for short, AVD) total-$k$-coloring of a graph $G$ is a proper total-$k$-coloring of $G$ such that any two adjacent vertices have different color sets, where the color set of a vertex $v$ contains the color of $v$ and the colors of its incident edges. It was conjectured that any graph with maximum degree $\Delta$ has an AVD total-($\Delta +3$)-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-($\Delta +2$)-coloring and the bound $\Delta +2$ is sharp.     

Proportional choosability: A new list analogue of equitable coloring

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L\left(v\right)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L\left(v\right)$. For each color $c$, let $\eta \left(c\right)$ be the number of vertices $v$ whose list $L\left(v\right)$ contains $c$. A proportional$L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {?}_{v\in V\left(G\right)}L\left(v\right)$ is used $?\eta \left(c\right)∕k?$ or $?\eta \left(c\right)∕k?$ times. A graph $G$ is proportionally$k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k\ge \Delta \left(G\right)+?\left|V\left(G\right)\right|∕2?$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.     

Improved square coloring of planar graphs

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac{3}{2}\mathrm{\Delta }+1$ colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2\mathrm{\Delta }+7$ colors are sufficient, which improves the best known bounds when $6?\mathrm{\Delta }?31$.     

A note on one-sided interval edge colorings of bipartite graphs

For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by ${\chi }_{int}^{\prime }(G,X)$ the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial $P(\mathrm{\Delta })$ such that if G has maximum degree at most Δ, then ${\chi }_{int}^{\prime }(G,X)\le P(\mathrm{\Delta })$. In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on ${\chi }_{int}^{\prime }(G,X)$ for bipartite graphs with small maximum degree.     

A tight bound for conflict-free coloring in terms of distance to cluster

Given an undirected graph $G=(V,E)$, a conflict-free coloring with respect to open neighborhoods (CFON coloring) is a vertex coloring such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for such a coloring is the CFON chromatic number of G, denoted by ${\chi }_{ON}(G)$.In previous work [WG 2020], we showed the upper bound ${\chi }_{ON}(G)\le \mathsf{dc}(G)+3$, where $\mathsf{dc}(G)$ denotes the distance to cluster parameter of G. In this paper, we obtain the improved upper bound of ${\chi }_{ON}(G)\le \mathsf{dc}(G)+1$. We also exhibit a family of graphs for which ${\chi }_{ON}(G)>\mathsf{dc}(G)$, thereby demonstrating that our upper bound is tight.     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

Quasisymmetric and Schur expansions of cycle index polynomials

Given a subgroup $G$ of the symmetric group $S_n$, the cycle index polynomial ${\mathrm{cyc}}_G$ is the average of the power-sum symmetric polynomials indexed by the cycle types of permutations in $G$. By Pólya’s Theorem, the monomial expansion of ${\mathrm{cyc}}_G$ is the generating function for weighted colorings of $n$ objects, where we identify colorings related by one of the symmetries in $G$. This paper develops combinatorial formulas for the fundamental quasisymmetric expansions and Schur expansions of certain cycle index polynomials. We give explicit bijective proofs based on standardization algorithms applied to equivalence classes of colorings. Subgroups studied here include Young subgroups of $S_n$, the alternating groups $A_n$, direct products, conjugate subgroups, and certain cyclic subgroups of $S_n$ generated by $(1,2,\dots ,k)$. The analysis of these cyclic subgroups when $k$ is prime reveals an unexpected connection to perfect matchings on a hypercube with certain vertices identified.     

Proximity and remoteness in triangle-free and C4-free graphs in terms of order and minimum degree

Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness $\rho (G)$ and the proximity $\pi (G)$ of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of $C_4$-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.