Colouring of generalized signed triangle-free planar graphs

We view an undirected graph $G$ as a symmetric digraph, where each edge $xy$ is replaced by two opposite arcs $e=(x,y)$ and $e^{?1}=(y,x)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $\sigma :E\left(G\right)\to S$ with $\sigma (x,y)={\left(\sigma (y,x)\right)}^{?1}$, there is a mapping $f:V\left(G\right)\to \left[k\right]=\{1,2,\dots ,k\}$ such that ${\sigma }_e\left(f\left(x\right)\right)\ne f\left(y\right)$ for each arc $e=(x,y)$. The concept of $S$-$k$-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets $S$ such that every triangle-free planar graph is $S$-3-colourable. Such a set $S$ is called TFP-good. Grötzsch’s theorem is equivalent to say that $S=\left\{id\right\}$ is TFP-good. We prove that for any inverse closed subset $S$ of $S_3$ which is not isomorphic to $\{id,\left(12\right)\}$, $S$ is TFP-good if and only if either $S=\left\{id\right\}$ or there exists $a\in \left[3\right]$ such that for each $\pi \in S$, $\pi \left(a\right)\ne a$. It remains an open question to determine whether or not $S=\{id,\left(12\right)\}$ is TFP-good.     

Oddness to resistance ratios in cubic graphs

Let $G$ be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of $G$, denoted as $\omega \left(G\right)$ (Steffen, 2004) (${\omega }^{\prime }\left(G\right)$ Lukot’ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot’ka and Mazák, 2016, Lukot’ka et al., 2015 and, Steffen, 2004), due to the fact that $\omega \left(G\right)=0$ and ${\omega }^{\prime }\left(G\right)=0$ if and only if $G$ is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from $G$ such that the resulting graph is 3-edge-colourable, denoted as $r\left(G\right)$ (Steffen, 2004). It is easily shown that $\omega \left(G\right)\ge {\omega }^{\prime }\left(G\right)\ge r\left(G\right)$. While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ${\omega }^{\prime }\left(G\right)\le 2r\left(G\right)$, and that if $G$ is a snark then $\omega \left(G\right)\le 2r\left(G\right)$ (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility, and hypothesizing that almost all cubic graphs are such resistance reducible.     

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$.     

Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

For any graph $G$ with $a,b\in V\left(G\right)$, a shortest path reconfiguration graph can be formed with respect to $a$ and $b$; we denote such a graph as $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths from $a$ to $b$ in $G$ while two vertices $U,W$ in $V\left(S(G,a,b)\right)$ are adjacent if and only if the vertex sets of the paths that represent $U$ and $W$ differ in exactly one vertex. In a recent paper (Asplund et al., 2018), it was shown that shortest path graphs with girth five or greater are exactly disjoint unions of even cycles and paths. In this paper, we extend this result by classifying all shortest path graphs with no induced 4-cycles.     

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.     

A new arithmetic criterion for graphs being determined by their generalized Q-spectrum

“Which graphs are determined by their spectrum (DS for short)?” is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized $Q$-spectrum. A graph $G$ is said to be determined by the generalized $Q$-spectrum (DGQS for short) if, for any graph $H$, $H$ and $G$ have the same $Q$-spectrum and so do their complements imply that $H$ is isomorphic to $G$. We give a simple arithmetic condition for a graph being DGQS. More precisely, let $G$ be a graph with adjacency matrix $A$ and degree diagonal matrix $D$. Let $Q=A+D$ be the signless Laplacian matrix of $G$, and $W_Q\left(G\right)=[e,Qe,\dots ,Q^{n-1}e]$ ($e$ is the all-ones vector) be the $Q$-walk matrix. We show that if $\frac{det{W}_Q\left(G\right)}{2^{\lfloor \frac{3n-2}{2}\rfloor }}$ (which is always an integer) is odd and square-free, then $G$ is DGQS.     

Average degrees of edge-chromatic critical graphs

Let $G$ be a simple graph, and let $\Delta \left(G\right)$, $\overline{d}\left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree, the average degree and the chromatic index of $G$, respectively. We called $G$ edge-$\Delta$-critical if ${\chi }^{\prime }\left(G\right)=\Delta \left(G\right)+1$ and ${\chi }^{\prime }\left(H\right)\le \Delta \left(G\right)$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is an edge-$\Delta$-critical graph of order $n$, then $\overline{d}\left(G\right)\ge \Delta \left(G\right)?1+\frac{3}{n}$. We prove that for any edge-$\Delta$-critical graph $G$, $\stackrel{?}{d}\left(G\right)\ge min\left\{\frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1},\frac{3\Delta \left(G\right)}{4}?2\right\},$ that is, $\overline{d}\left(G\right)\ge \left\{\begin{array}{cc}\frac{3}{4}\Delta \left(G\right)?2\hfill & \text{if}\Delta \left(G\right)\le 75;\hfill \\ \frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1}\approx 0.7388\Delta \left(G\right)?1.153\hfill & \text{if}\Delta \left(G\right)\ge 76.\hfill \end{array}\right.$This result improves the best known bound $\frac{2}{3}(\Delta \left(G\right)+2)$ obtained by Woodall in 2007 for $\Delta \left(G\right)\ge 41$.     

Biased graphs. VI. synthetic geometry

A biased graph is a graph with a class of selected circles (“cycles”, “circuits”), called balanced, such that no theta subgraph contains exactly two balanced circles. A biased graph $\Omega$ has two natural matroids, the frame matroid $G\left(\Omega \right)$ and the lift matroid $L\left(\Omega \right)$, and their extensions the full frame matroid $G^{•}\left(\Omega \right)$ and the extended (or complete) lift matroid $L_0\left(\Omega \right)$. In Part IV we used algebra to study the representations of these matroids by vectors over a skew field and the corresponding embeddings in Desarguesian projective spaces. Here we redevelop those representations, independently of Part IV and in greater generality, by using synthetic geometry.     

Spectral results on Hamiltonian problem

Let $\alpha$ be a non-negative real number, and let $\Theta (G,\alpha )$ be the largest eigenvalue of $A\left(G\right)+\alpha D\left(G\right)$. Specially, $\Theta (G,0)$ and $\Theta (G,1)$ are called the spectral radius and signless Laplacian spectral radius of $G$, respectively. A graph $G$ is said to be Hamiltonian (traceable) if it contains a Hamiltonian cycle (path), and a graph $G$ is called Hamilton-connected if any two vertices are connected by a Hamiltonian path in $G$. The number of edges of $G$ is denoted by $e\left(G\right)$. Recently, the (signless Laplacian) spectral property of Hamiltonian (traceable, Hamilton-connected) graphs received much attention. In this paper, we shall give a general result for all these existed results. To do this, we first generalize the concept of Hamiltonian, traceable, and Hamilton-connected to $s$-suitable, and we secondly present a lower bound for $e\left(G\right)$ to confirm the existence of $s$-suitable graphs. Thirdly, when $0\le \alpha \le 1$, we obtain a lower bound for $\Theta (G,\alpha )$ to confirm the existence of $s$-suitable graphs. Consequently, our results generalize and improve all these existed results in this field, including the main results of Chen et al. (2018), Feng et al. (2017), Füredi et al. (2017), Ge et al. (2016), Li et al. (2016), Nikiforov et al. (2016), Wei et al. (2019) and Yu et al. (2013, 2014).     

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.