A \((k, t)\)-list assignment \(L\) of a graph \(G\) assigns a list of \(k\) colors available at each vertex \(v\) in \(G\) and \(|\bigcup_{v\in V(G)}L(v)| = t\). An \(L\)-coloring is a proper coloring \(c\) such that \(c(v) \in L(v)\) for each \(v \in V(G)\). A graph \(G\) is \((k,t)\)-choosable if \(G\) has an \(L\)-coloring for every \((k, t)\)-list assignment \(L\).
Erdős, Rubin, and Taylor proved that a graph is \((2, t)\)-choosable for any \(t > 2\) if and only if a graph does not contain some certain subgraphs. Chareonpanitseri, Punnim, and Uiyyasathian proved that an \(n\)-vertex graph is \((2,t)\)-choosable for \(2n – 6 \leq t \leq 2n – 4\) if and only if it is triangle-free. Furthermore, they proved that a triangle-free graph with \(n\) vertices is \((2, 2n – 7)\)-choosable if and only if it does not contain \(K_{3,3} – e\) where \(e\) is an edge. Nakprasit and Ruksasakchai proved that an \(n\)-vertex graph \(G\) that does not contain \(C_5 \vee K_{n-2}\) and \(K_{4,4}\) for \(k \geq 3\) is \((k, kn – k^2 – 2k)\)-choosable. For a non-2-choosable graph \(G\), we find the minimum \(t_1 \geq 2\) and the maximum \(t_2\) such that the graph \(G\) is not \((2, t_i)\)-choosable for \(i = 1, 2\) in terms of certain subgraphs. The results can be applied to characterize \((2, t)\)-choosable graphs for any \(t\).

Let \(G\) be the circuit graph of any connected matroid. It is proved that the circuit graph of a connected matroid with at least three circuits is \(E_2\)-Hamiltonian.

The Randić index \(R(G)\) of a graph \(G\) is defined by \(R(G) = \sum\limits_{uv} \frac{1}{\sqrt{d(u)d(v)}}\), where \(d(u)\) is the degree of a vertex \(u\) in \(G\) and the summation extends over all edges \(uv\) of \(G\). In this work, we give sharp lower bounds of \(R(G) + g(G)\) and \(R(G) . g(G)\) among \(n\)-vertex connected triangle-free graphs with Randić index \(R\) and girth \(g\).

Hammack and Livesay introduced a new graph operation \(G^{(k)}\) for a graph \(G\), which they called the \(k\)th inner power of \(G\). A graph \(G\) is Hamiltonian if it contains a spanning cycle. In this paper, we show that \(C^{(k)}_n(n \geq 3, k \geq 2)\) is Hamiltonian if and only if \(n\) is odd and \(k = 2\), where \(C_n\) is the cycle with \(n\) vertices.

Let \(a(v)\) and \(g(v)\) denote the least possible area and the least possible number of lattice points in the interior of a convex lattice \(v\)-gon, respectively. Many lower and upper bounds for \(a(v)\) and \(g(v)\) are known for every \(v\). However, the exact values of these two functions are only known for \(v \leq 10\) and \(v \in \{12, 13, 14, 16, 18, 20, 22\}\). The purpose of this paper is to answer the following Open Question 1 from \([13]\): What is the exact value of \(a(11)\)? We answer this question by proving that \(a(11) = 21.5\). On our way to achieve this goal, we also prove that \(g(11) = 17\).

The edge-face total chromatic number of \(3\)-regular Halin graphs was shown to be \(4\) or \(5\) in \([5]\). In this paper, we shall provide a necessary and sufficient condition to characterize \(3\)-regular Halin graphs with edge-face total chromatic number equal to four.

Jaeger \(et \;al\). [ J. Combin. Theory, Ser B, \(56 (1992) 165-182]\) conjectured that every 3-edge-connected graph is \(Z_5\)-connected. Let \(G\) be a 3-edge-connected simple graph on \(n\) vertices and \(A\) an abelian group with \(|A| \geq 3\). If a graph \(G^*\) is obtained by repeatedly contracting nontrivial \(A\)-connected subgraphs of \(G\) until no such subgraph is left, we say \(G\) can be \(A\)-reduced to \(G^*\). It is proved in this paper that \(G\) is \(A\)-connected with \(|A| \geq 5\) if one of the following holds: (i) \(n \leq 15\); (ii) \(n = 16\) and \(\Delta \geq 4\); or (iii) \(n = 17\) and \(\Delta \geq 5\). As applications, we also show the following results:
(1) For \(|A| \geq 5\) and \(n \geq 17\), if \(|E(G)| \geq \binom{n-15}{2} + 31\), then \(G\) is \(A\)-connected.
(2) For \(|A| \geq 4\) and \(n \geq 13\), if \(|E(G)| \geq \binom{n-11}{2} + 23\), then either \(G\) is \(A\)-connected or \(G\) can be \(A\)-reduced to the Petersen graph.

Given a partial cube \(G\), the \(\Theta\)-graph of \(G\) has \(\Theta\)-classes of \(G\) as its vertices, and two vertices in it are adjacent if the corresponding \(\Theta\)-classes meet in a vertex of \(G\). We present a counter-example to the question from \([8]\) whether \(\Theta\)-graphs of graphs of acyclic cubical complexes are always dually chordal graphs. On a positive side, we show that in the class of ACC \(p\)-expansion graphs, each \(\Theta\)-graph is both a dually chordal and a chordal graph. In the proof, a fundamental characterization of \(\Theta\)-acyclic hypergraphs is combined with techniques from metric graph theory. Along the way, we also introduce a new, weaker version of simplicial elimination scheme, which yields yet another characterization of chordal graphs.

Let \(X = (V, E)\) be a connected vertex-transitive graph with degree \(k\). Call \(X\) super restricted edge-connected, in short, sup-\(\lambda’\), if \(F\) is a minimum edge set of \(X\) such that \(X – F\) is disconnected and every component of \(X – F\) has at least two vertices, then \(F\) is the set of edges adjacent to a certain edge in \(X\). Wang [Y, Q, Wang, Super restricted edge-connectivity of vertex-transitive graphs, Discrete Mathematics \(289 (2004) 199-205]\) proved that a connected vertex-transitive graph with degree \(k > 2\) and girth \(g > 4\) is sup-\(\lambda’\). In this paper, by studying the \(k\)-superatom of \(X\), we present sufficient and necessary conditions for connected vertex-transitive graphs and Cayley graphs with degree \(k > 2\) to be sup-\(\lambda’\). In particular, sup-\(\lambda’\) connected vertex-transitive graphs with degree \(k > 2\) and girth \(g > 3\) are completely characterized. These results can be seen as an improvement of the one obtained by Wang.

A proper vertex coloring of a graph \(G\) is called a dynamic coloring if for every vertex \(v\) with degree at least 2, the neighbors of \(v\) receive at least two different colors. It was conjectured that if \(G\) is a regular graph, then \(\chi_2(G) – \chi(G) \leq 2\). In this paper, we prove that, apart from the cycles \(C_4\) and \(C_5\) and the complete bipartite graphs \(K_{n,n}\), every strongly regular graph \(G\) satisfies \(\chi_2(G) – \chi(G) \leq 1\).