Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

On the size of special class 1 graphs and (P3;k)-co-critical graphs

A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index ${\chi }^{\prime }(G)$ of G is Δ or $\mathrm{\Delta }+1$. A graph G is class 1 if ${\chi }^{\prime }(G)=\mathrm{\Delta }$, and class 2 if ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$; G is Δ-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least $(n(\mathrm{\Delta }-1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\bar{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph G is $(P_3;k)$-co-critical if there exists a k-coloring of $E(G)$ such that G does not contain a monochromatic copy of $P_3$ but every k-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\bar{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if G is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then$e(G)\ge \frac{k}{2}(n-\lceil \frac{k}{2}\rceil -\epsilon )+\left(\begin{array}{c}\lceil k/2\rceil +\epsilon \\ 2\end{array}\right),$ where ε is the remainder of $n-\lceil k/2\rceil$ when divided by 2. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.     

Arithmetic invariants from Sato–Tate moments

We give some arithmetic-geometric interpretations of the moments ${\mathrm{M}}_2[a_1]$, ${\mathrm{M}}_1[a_2]$, and ${\mathrm{M}}_1[s_2]$ of the Sato–Tate group of an abelian variety A defined over a number field by relating them to the ranks of the endomorphism ring and Néron–Severi group of A.     

GE2-rings and a graph of unimodular rows

For a commutative ring A we consider a related graph, $\mathrm{\Gamma }(A)$, whose vertices are the unimodular rows of length 2 up to multiplication by units. We prove that $\mathrm{\Gamma }(A)$ is path-connected if and only if A is a ${\mathrm{GE}}_2$-ring, in the terminology of P. M. Cohn. Furthermore, if $Y(A)$ denotes the clique complex of $\mathrm{\Gamma }(A)$, we prove that $Y(A)$ is simply connected if and only if A is universal for ${\mathrm{GE}}_2$. More precisely, our main theorem is that for any commutative ring A the fundamental group of $Y(A)$ is isomorphic to the group $K_2(2,A)$ modulo the subgroup generated by symbols.     

Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets

An $(m,n)$-colored-mixed graph $G=(V,A_1,A_2,\cdots ,A_m,E_1,E_2,\cdots ,E_n)$ is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$-colored-mixed graph G to another $(m,n)$-colored-mixed graph H is a morphism $\phi :V(G)\to V(H)$ such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An $(m,n)$-colored-mixed graph T is said to be $P_g^{(m,n)}$-universal if every graph in $P_g^{(m,n)}$ (the planar $(m,n)$-colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar $P_g^{(m,n)}$-universal graphs do not exist for $2m+n\ge 3$ (and any value of g) and find a minimal (in the number vertices) planar $P_g^{(m,n)}$-universal graphs in the other cases.     

Existence of solutions of a non-linear eigenvalue problem with a variable weight

We study the non-linear minimization problem on $H_0^1(\mathrm{\Omega })?L^q$ with $q=\frac{2n}{n?2}$, $\alpha >0$ and $n\ge 4$:

$\underset{\begin{array}{c}\hfill u\in H_0^1(\mathrm{\Omega })\hfill \\ \hfill {6u6}_{L^q}=1\hfill \end{array}}{\inf }?\underset{\mathrm{\Omega }}{\int }a(x,u)|\mathrm{?}u{|}^2?\lambda \underset{\mathrm{\Omega }}{\int }|u{|}^2$

where $a(x,s)$ presents a global minimum α at $(x_0,0)$ with $x_0\in \mathrm{\Omega }$. In order to describe the concentration of $u(x)$ around $x_0$, one needs to calibrate the behavior of $a(x,s)$ with respect to s. The model case is

$\underset{\begin{array}{c}\hfill u\in H_0^1(\mathrm{\Omega })\hfill \\ \hfill {6u6}_{L^q}=1\hfill \end{array}}{\inf }?\underset{\mathrm{\Omega }}{\int }(\alpha +|x{|}^{\beta }|u{|}^k)|\mathrm{?}u{|}^2?\lambda \underset{\mathrm{\Omega }}{\int }|u{|}^2.$

In a previous paper dedicated to the same problem with $\lambda =0$, we showed that minimizers exist only in the range $\beta <kn/q$, which corresponds to a dominant non-linear term. On the contrary, the linear influence for $\beta \ge kn/q$ prevented their existence. The goal of this present paper is to show that for $0<\lambda \le \alpha {\lambda }_1(\mathrm{\Omega })$, $0\le k\le q?2$ and $\beta >kn/q+2$, minimizers do exist.