The σ -irregularity, a variant of the well-established Albertson irregularity, is a topological invariant defined for a graph G = ( V , E ) as σ ( G ) = ∑ u v ∈ E ( d ( u ) − d ( v ) ) 2 , where d ( u ) and d ( v ) denote the degrees of vertices u and v , respectively. Recent research has successfully characterized chemical trees with the maximum σ -irregularity. In this paper, we expand upon this research by establishing several structural properties of maximal trees with prescribed maximum degree Δ . Application of these properties enables us to characterize maximal trees with Δ = 5 . We establish that extremal trees contain only vertices of degrees 1 , 2 and Δ . Moreover, the number of edges with both end-vertices having the degree 2 or Δ is very small, so almost all edges have the (second) maximum possible contribution to σ -irregularity. We believe this property or similar should extend to maximal trees for any value of Δ , so this is an interesting direction for further research.

In this short paper, we introduce a new vertex coloring whose motivation comes from our series on odd edge-colorings of graphs. A proper vertex coloring φ of a graph G is said to be odd if for each non-isolated vertex x∈V(G) there exists a color c such that φ−1(c)∩N(x) is odd-sized. We prove that every simple planar graph admits an odd 9-coloring, and conjecture that 5 colors always suffice.

The Wiener index W(G) of a connected graph G is defined to be the sum of distances between all pairs of vertices in G. In 1991, Šoltés studied changes of the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs G so that equality W(G)=W(G−v) holds for all their vertices v. The cycle with 11 vertices is still the only known graph with this property. In this paper we study a relaxed version of this problem and find graphs which Wiener index does not change when a particular vertex v is removed. We show that there is a unicyclic graph G on n vertices with W(G)=W(G−v) if and only if n≥9. Also, there is a unicyclic graph G with a cycle of length c for which W(G)=W(G−v) if and only if c≥5. Moreover, we show that every graph G is an induced subgraph of H such that W(H)=W(H−v). As our relaxed version is rich with solutions, it gives hope that Šoltes’s problem may have also some solutions distinct from C11.

A queue layout of a graph consists of a linear ordering $\sigma$ of its vertices and a partition of its edges into sets, called queues, such that in each set no two edges are nested with respect to $\sigma$. We show that the n-dimensional hypercube $Q_n$ has a layout into $n-\lfloor \log_2 n \rfloor$ queues for all $n\ge 1$. On the other hand, for every $\varepsilon>0$, every queue layout of $Q_n$ has more than $(\frac{1}{2}-\varepsilon) n-O(1/\varepsilon)$ queues and, in particular, more than $(n-2)/3$ queues. This improves previously known upper and lower bounds on the minimal number of queues in a queue layout of $Q_n$. For the lower bound we employ a new technique of out-in representations and contractions which may be of independent interest.

A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. Thomassen's theorem states that every planar graph is 5-choosable. We extend the result by showing that every graph with at most two crossings is 5-choosable.

Let [Formula: see text] denote the set of all odd cycle lengths of a graph [Formula: see text]. Gyárfás gave an upper bound for [Formula: see text] depending on the size of this set: if [Formula: see text], then [Formula: see text] unless some block of [Formula: see text] is a [Formula: see text], in which case [Formula: see text]. This bound is generally tight, but when investigating [Formula: see text] of special forms, better results can be obtained. Wang completely analyzed the case [Formula: see text]; Camacho proved that if [Formula: see text], [Formula: see text], then [Formula: see text]. We show that [Formula: see text] implies [Formula: see text].

We show that every pair of hexagons in a fullerene graph satisfying the isolated pentagon rule (IPR) forms a resonant pattern. This solves a problem raised by Ye, Qi, and Zhang [SIAM J. Discrete Math., 23 (2009), pp. 1023–1044].

A graph is k-choosable if it can be colored whenever every vertex has a list of at least k available colors. We prove that if a triangle-free planar graph is not 3-choosable, then it contains a 4-cycle that intersects another 4- or 5-cycle in exactly one edge. This strengthens Thomassen's result [C. Thomassen, J. Combin. Theory Ser. B, 64 (1995), pp. 101–107] that every planar graph of girth at least 5 is 3-choosable. In addition, this implies that every triangle-free planar graph without 6- and 7-cycles is 3-choosable.

A well-known result (Heawood [Quart. J. Pure Appl. Math., 24 (1890), pp. 332–338], Ringel [Map Color Theorem, Springer-Verlag, New York, 1974], Ringel and Youngs [Proc. Nat. Acad. Sci., U.S.A., 60 (1968), pp. 438–445]) states that the maximum chromatic number of a graph embedded in a given surface S coincides with the size of the largest clique that can be embedded in S, and that this number can be expressed as a simple formula in the Euler genus of S. A partition of a graph G into k parts consists of k edge-disjoint subgraphs $G_1,\dots,G_k$ such that $E(G)=E(G_1)\cup E(G_2)\cup\dots\cup E(G_k)$. The k-chromatic number $\chi_k (G)$ is the maximum of $\sum_{i=1}^k\chi(G_i)$ over all partitions of G into k parts. We derive a Heawood-type formula for the k-chromatic number of graphs embedded in a fixed surface, improving the previously known upper bounds. In infinitely many cases, the new upper bound coincides with the lower bound obtained from embedding disjoint cliques in the surface. In the proof of this result, we derive a variant of Euler's formula for the union of several graphs that might be interesting independently.

For a graph G and its spanning tree T the backbone chromatic number, $\mathrm{BBC}(G,T)$, is defined as the minimum k such that there exists a coloring $c\colon V(G)\rightarrow\{1,2,\dots,k\}$ satisfying $|c(u)-c(v)|\geq1$ if $uv\in E(G)$ and $|c(u)-c(v)|\geq2$ if $uv\in E(T)$. Broersma et al. [J. Graph Theory, 55 (2007), pp. 137–152] asked whether there exists a constant c such that for every triangle-free graph G with an arbitrary spanning tree T the inequality $\mathrm{BBC}(G,T)\leq\chi(G)+c$ holds. We answer this question negatively by showing the existence of triangle-free graphs $R_n$ and their spanning trees $T_n$ such that $\mathrm{BBC}(R_n,T_n)=2\chi(R_n)-1=2n-1$. In order to answer the question, we obtain a result of independent interest. We modify the well-known Mycielski construction and construct triangle-free graphs $J_n$ for every integer n, with chromatic number n and 2-tuple chromatic number $2n$ (here 2 can be replaced by any integer t).

The problem of coloring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider this problem for sparse subcubic graphs. We show that the choosability $\chi_\ell(G^2)$ of the square of a subcubic graph G of maximum average degree d is at most four if $d<24/11$ and G does not contain a 5-cycle, at most five if $d<7/3$, and at most six if $d<5/2$. Wegner's conjecture claims that the chromatic number of the square of a subcubic planar graph is at most seven. Let G be a planar subcubic graph of girth g. Our result implies that $\chi_\ell(G^2)$ is at most four if $g\ge 24$, at most 5 if $g\ge 14$, and at most 6 if $g\ge 10$. For lower bounds, we find a planar subcubic graph $G_1$ of girth 9 such that $\chi(G_1^2)=5$ and a planar subcubic graph $G_2$ of girth 5 such that $\chi(G_2^2)=6$. As a consequence, we show that the problem of 4-coloring of the square of a subcubic planar graph of girth $g=9$ is NP-complete. We conclude the paper by posing a few conjectures.

Let G be a graph and let $c: V(G)\to\binom{1,\ldots,5}{2}$ be an assignment of 2-element subsets of the set $1,\ldots,5$ to the vertices of G such that for every edge $vw$, the sets $c(v)$ and $c(w)$ are disjoint. We call such an assignment a $(5,2)$-coloring. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph. The odd-girth of a graph G is the length of the shortest odd cycle in G ($\infty$ if G is bipartite). We prove that every planar graph of odd-girth at least 9 is $(5,2)$-colorable, and thus it is homomorphic to the Petersen graph. Also, this implies that such graphs have a fractional chromatic number at most $5\over2$. As a special case, this result holds for planar graphs of girth at least 8.

A plane graph is ł-facially k-colorable if its vertices can be colored with k colors such that any two distinct vertices on a facial segment of length at most łare colored differently. We prove that every plane graph is 3-facially $11$-colorable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically $11$-colorable. These two bounds are just one higher than those that are proposed by the $(3\l+1)$-conjecture and the cyclic conjecture.

We prove that every cubic bridgeless graph G contains a 2-factor which intersects all (minimal) edge-cuts of size 3 or 4. This generalizes an earlier result of the authors, namely that such a 2-factor exists provided that G is planar. As a further extension, we show that every graph contains a cycle (a union of edge-disjoint circuits) that intersects all edge-cuts of size 3 or 4. Motivated by this result, we introduce the concept of a coverable set of integers and discuss a number of questions, some of which are related to classical problems of graph theory such as Tutte's 4-flow conjecture and the Dominating Cycle Conjecture.

The central problem of the total-colorings is the total-coloring conjecture, which asserts that every graph of maximum degree $\Delta$ admits a $(\Delta+2)$-total-coloring. Similar to edge-colorings—with Vizing's edge-coloring conjecture—this bound can be decreased by 1 for plane graphs of higher maximum degree. More precisely, it is known that if $\Delta\ge10$, then every plane graph of maximum degree $\Delta$ is $(\Delta+1)$-totally-colorable. On the other hand, such a statement does not hold if $\Delta\le3$. We prove that every plane graph of maximum degree 9 can be 10-totally-colored.

An edge of a graph is light when the sum of the degrees of its end‐vertices is at most 13. The well‐known Kotzig theorem states that every 3‐connected planar graph contains a light edge. Later, Borodin [J. Reine Angew. Math., 394 (1989), pp. 180–185] extended this result to the class of planar graphs of minimum degree at least 3. We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka, and Woodall [J. Combin. Theory Ser. B, 71 (1997), pp. 184–204] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2‐alternating cycles and 3‐alternators. This implies that planar graphs with maximum degree $\Delta \geq 12$ are $\Delta$‐edge‐choosable. We prove a similar result with 2‐alternating cycles and 3‐alternators replaced by five fixed bounded‐sized configurations called crowns. This gives another proof of $\Delta$‐edge‐choosability of planar graphs with $\Delta \geq 12$. However, we show efficient choosability; i.e., we describe a linear‐time algorithm for $\max\{\Delta,12\}$‐edge‐list‐coloring planar graphs. This extends the result of Chrobak and Yung [J. Algorithms, 10 (1989), pp. 35–51].

In 1955 Kotzig [A. Kotzig, Math. Slovaca, 5 (1955), pp. 111-113] proved that every planar 3-connected graph contains an edge such that the sum of degrees of its end-vertices is at most $13$. Moreover, if the graph does not contain 3-vertices, then this sum is at most $11$. Such an edge is called light. The well-known result of Steinitz [E. Steinitz, Enzykl. Math. Wiss., 3 (1922), pp. 1-139] that the 3-connected planar graphs are precisely the skeletons of 3-polytopes gives an additional trump to Kotzig's theorem. On the other hand, in 1961, Tutte [W. T. Tutte, Indag. Math., 23 (1961), pp. 441-455] proved that every 3-connected graph, distinct from $K_4$, contains a contractible edge. In this paper, we strengthen Kotzig's theorem by showing that every 3-connected planar graph distinct from $K_4$ contains an edge that is both light and contractible. A consequence is that every 3-polytope can be constructed from tetrahedron by a sequence of splittings of vertices of degree at most $11$.

An L(2,1)-labeling of a graph G is a mapping c : V(G) \to {0,...,K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. A hole of c is an integer h \in {0,...,K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2,1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro [SIAM J. Discrete Math., 19 (2005), pp. 208-223] showed that rho(G) \le Delta, where Delta is the maximum degree of G, and conjectured that if rho(G) = Delta and G is connected, then the order of G is at most Delta(Delta + 1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order \lfloor (Delta + 1) 2 /4 \rfloor (Delta + 1) \approx Delta 3 /4.

We study the notion of a generalized list T-coloring which is a common generalization of the channel assignment problem and the T-coloring. An instance of the generalized list T-coloring is described by a triple $(G,\Lambda,t)$, where G is a graph, $\Lambda$ is a mapping which assigns the vertices of G lists of numbers (colors), and t is a mapping which assigns each edge of G a set of forbidden differences. We require that $0\in t(e)$ for each edge e of G. The goal is to find a labeling c of the vertices of G with $c(v)\in\Lambda(v)$ for each vertex v, and $|c(u)-c(v)|\not\in t(uv)$ for each edge $uv$ of G. An instance is balanced if the size of the list $\Lambda(v)$ for each vertex v is equal to the sum of the sizes of $t(e)$ for edges e incident with v. We state and prove a Brooks-type theorem for the generalized list T-coloring problem. This generalizes and unifies the previously known Brooks-type theorems for the channel assignment problem and for the T-coloring. The theorem characterizes balanced instances of the generalized list T-coloring with a good labeling. As a consequence, if G is a connected graph different from a Gallai tree, then all balanced instances on G have good labelings.

A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\in L(v)$ for each vertex v and $|c(u)-c(v)|\ge w(uv)$ for each edge uv. A weighted degree $\deg_w(v)$ of a vertex v is the sum of the weights of the edges incident with v. If G is connected, $|L(v)|>\deg_w(v)$ for at least one v, and $|L(v)|\ge\deg_w(v)$ for all v, then a proper coloring always exists. A list channel assignment problem is balanced if $|L(v)|=\deg_w(v)$ for all v. We characterize all balanced list channel assignment problems (G,L,w) which admit a proper coloring. An application of this result is that each graph with maximum degree $\Delta\ge 2$ has an L(2,1)-labeling using integers $0,\ldots,\Delta^2+\Delta-1$.