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

Strong edge-coloring for planar graphs with large girth

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. Let $G$ be a connected planar graph with girth $k\ge 26$ and maximum degree $\Delta$. We show that either $G$ is isomorphic to a subgraph of a very special $\Delta$-regular graph with girth $k$, or $G$ has a strong edge-coloring using at most $2\Delta +\lceil \frac{12(\Delta -2)}{k}\rceil$ colors.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

A constructive characterization of contraction critical 8-connected graphs with minimum degree 9

An edge of a $k$-connected graph is said to be $k$-contractible if its contraction results in a $k$-connected graph. A $k$-connected graph without $k$-contractible edge is said to be contraction critically $k$-connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical $k$-connected graph is at most $\frac{5k}{4}?1$. Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph $G$ is a contraction critical 8-connected graph with minimum degree 9 if and only if $G$ is the strong product of a contraction critical 4-connected graph $H$ and $K_2$.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Largest regular multigraphs with three distinct eigenvalues

We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k\ne 2,3,7,57$, we show an upper bound $n\le k^2?k+1$, with equality if and only if there exists a finite projective plane of order $k?1$ that admits a polarity.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints

Let $k\ge 4$ and $n\ge k+4$ be positive integers. We determine the maximum size of digraphs of order $n$ that avoid distinct walks of length $k$ with the same endpoints. We also characterize the extremal digraphs attaining this maximum number when $k\ge 5$.     

3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices

Let $g(k,t)$ be the minimum integer such that every plane graph with girth g at least $g(k,t)$, minimum degree $\delta =2$ and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge 1$, has a 3-vertex with at least t neighbors of degree 2, where $1\le t\le 3$.In 2015, Jendrol' and Maceková proved $g(1,1)\le 7$. Later on, Hudák et al. established $g(1,3)=10$, Jendrol', Maceková, Montassier, and Soták proved $g(1,1)\ge 7$, $g(1,2)=8$ and $g(2,2)\ge 11$, and we recently proved that $g(2,2)=11$ and $g(2,3)=14$.Thus $g(k,t)$ is already known for $k=1$ and all t. In this paper, we prove that $g(k,1)=3k+4$, $g(k,2)=3k+5$, and $g(k,3)=3k+8$ whenever $k\ge 2$.     

Large induced subgraphs with three repeated degrees

For any positive integer k, let $C(k)$ denote the least integer such that any n-vertex graph has an induced subgraph with at least $n?C(k)$ vertices, in which at least $\min ?\{k,n?C(k)\}$ vertices are of the same degree. Caro, Shapira and Yuster initially studied this parameter and showed that $\mathrm{\Omega }(k\log ?k)\le C(k)\le {(8k)}^k$. For the first nontrivial case, the authors proved that $3\le C(3)\le 6$, and the exact value was left as an open problem. In this paper, we first show that $3\le C(3)\le 4$, improving the former result as well as a recent result of Kogan. For special families of graphs, we prove that $C(3)=3$ for $K_5$-free graphs, and $C(3)=1$ for large $C_{2s+1}$-free graphs. In addition, extending a result of Erd?s, Fajtlowicz and Staton, we assert that every $K_r$-free graph is an induced subgraph of a $K_r$-free graph in which no degree occurs more than three times.     

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.     

H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups

We consider the structure of $H$-free subgraphs of graphs with high minimal degree. We prove that for every $k>m$ there exists an $???(k,m)>0$ so that the following holds. For every graph $H$ with chromatic number $k$ from which one can delete an edge and reduce the chromatic number, and for every graph $G$ on $n>n_0\left(H\right)$ vertices in which all degrees are at least $(1??)n$, any subgraph of $G$ which is $H$-free and contains the maximum number of copies of the complete graph $K_m$ is $(k?1)$-colorable.We also consider several extensions for the case of a general forbidden graph $H$ of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs.     

On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

List-edge-colouring planar graphs with precoloured edges

Let $G$ be a simple planar graph of maximum degree $\Delta$, let $t$ be a positive integer, and let $L$ be an edge list assignment on $G$ with $\left|L\left(e\right)\right|\ge \Delta +t$ for all $e\in E\left(G\right)$. We prove that if $H$ is a subgraph of $G$ that has been $L$-edge-coloured, then the edge-precolouring can be extended to an $L$-edge-colouring of $G$, provided that $H$ has maximum degree $d\le t$ and either $d\le t-4$ or $\Delta$ is large enough ($\Delta \ge 16+d$ suffices). If $d>t$, there are examples for any choice of $\Delta$ where the extension is impossible.     

On the weak 2-coloring number of planar graphs

For a graph $G=(V,E)$, a total ordering L on V, and a vertex $v\in V$, let ${\mathrm{Wcol}}_2[G,L,v]$ be the set of vertices $w\in V$ for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is w. The weak 2-coloring number ${\mathrm{wcol}}_2(G)$ of G is the least k such that there is a total ordering L on V with $|{\mathrm{Wcol}}_2[G,L,v]|\le k$ for all vertices $v\in V$. We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved.     

Equitable defective coloring of sparse planar graphs

A graph has an equitable, defective $k$-coloring (an ED-$k$-coloring) if there is a $k$-coloring of $V\left(G\right)$ that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). A graph may have an ED-$k$-coloring, but no ED-$(k+1)$-coloring. In this paper, we prove that planar graphs with minimum degree at least $2$ and girth at least $10$ are ED-$k$-colorable for any integer $k\ge 3$. The proof uses the method of discharging. We are able to simplify the normally lengthy task of enumerating forbidden substructures by using Hall’s Theorem, an unusual approach.