The Classification Problem is the problem of deciding whether a simple graph has chromatic index equal to \(\Delta\) or \(\Delta + 1\), where \(\Delta\) is the maximum degree of the graph. It is known that deciding if a graph has chromatic index equal to \(4\) is \(NP\)-complete. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper, we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to \(\Delta\). Moreover, we present polynomial-time algorithms to perform an edge-coloring and to recognize these graphs.

Let \(K_4^-\) be the graph obtained from \(K_4\) by deleting one edge. A graph \(G\) is called \(K_4^-\)-free if it does not contain \(K_4^-\) as a subgraph. K. Kawarabayashi showed that a \(K_4^-\)-free \(k\)-connected graph has a \(k\)-contractible edge if \(k\) is odd. Furthermore, when \(k\) is even, K. Ando et al. demonstrated that every vertex of a \(K_4^-\)-free contraction critical \(k\)-connected graph is contained in at least two triangles. In this paper, we extend Kawarabayashi’s result and obtain a new lower bound on the number of \(k\)-contractible edges in a \(K_4^-\)-free \(k\)-connected graph when \(k\) is odd. Additionally, we provide characterizations and properties of \(K_4^-\)-free contraction critical \(k\)-connected graphs and prove that such graphs have at least \(\frac{2|G|}{k-1}\) vertices of degree \(k\).

Let \(D\) be a directed graph with \(n\) vertices and \(m\) edges. A function \(f: V(D) \to \{1, 2, 3, \ldots, k\}\), where \(k \leq n\), is said to be a harmonious coloring of \(D\) if for any two edges \(xy\) and \(uv\) of \(D\), the ordered pair \((f(x), f(y)) \neq (f(u), f(v))\). If the pair \((i, i)\) is not assigned, then \(f\) is said to be a proper harmonious coloring of \(D\). The minimum \(k\) is called the proper harmonious coloring number of \(D\). We investigate the proper harmonious coloring number of various graphs, including unidirectional paths, unicycles, inward-spoken (outward-spoken) wheels, \(n\)-ary trees of different levels, and others.

A vertex subset \(S\) of a digraph \(D = (V, A)\) is called an out-dominating (resp.,in-dominating) set of \(D\) if every vertex in \(V – S\) is adjacent from (resp., to) some vertex in \(S\). The out-domination (resp., in-domination) number of \(D\), denoted by \(\gamma^+(D)\) (resp.,\(\gamma^-(D)\)), is the minimum cardinality of an out-dominating (resp., in-dominating) set of \(D\). In 1999, Chartrand et al. proved that \(\gamma^+(D) + \gamma^-(D) \leq \frac{4n}{3}\) for every digraph \(D\) of order \(n\) with no isolated vertices. In this paper, we determine the values of \(\gamma^+(D) + \gamma^-(D)\) for rooted trees and connected contrafunctional digraphs \(D\), based on which we show that \(\gamma^+(D) + \gamma^-(D) \leq \frac{(2k+2)n}{2k+1}\) for every digraph \(D\) of order \(n\) with minimum out-degree or in-degree no less than \(1\), where \(2k + 1\) is the length of a shortest odd directed cycle in \(D\). Our result partially improves the result of Chartrand et al. In particular, if \(D\) contains no odd directed cycles, then \(\gamma^+(D) + \gamma^-(D) \leq n\).

Given graphs \(G\) and \(H\), an \(H\)-decomposition of \(G\) is a partition of the edge set of \(G\) such that each part is either a single edge or forms a graph isomorphic to \(H\). Let \(\gamma_H(n)\) denote the smallest number \(k\) such that any graph \(G\) of order \(n\) admits an \(H\)-decomposition with at most \(k\) parts. Here, we study the case when \(H = C_7\), the cycle of length \(7\), and prove that \(\gamma_{C_7}(n) = \left\lceil \frac{nZ^2}{4} \right\rceil\) for all \(n \geq 10\).

Given a (directed) graph \(G = (V, A)\), a subset \(X\) of \(V\) is an interval of \(G\) provided that for any \(a, b \in X\) and \(x \in V – X\), \((a, x) \in A\) if and only if \((b, x) \in A\) and \((x, a) \in A\)if and only if \((x, b) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(z \in V\)), and \(V\) are intervals of \(G\), called trivial intervals. A graph, all of whose intervals are trivial, is indecomposable; otherwise, it is decomposable. A vertex \(x\) of an indecomposable graph is critical if \(G – x\) is decomposable. In 1998, J.H. Schmerl and W.T. Trotter characterized the indecomposable graphs, all of whose vertices are critical, called critical graphs. In this article, we characterize the indecomposable graphs that admit a single non-critical vertex, which we term (-1)-critical graphs, answering a question posed by Y. Boudabbous and P. Ille in a recent article studying critical vertices in indecomposable graphs.

Let \(G\) be a graph with minimum degree \(\delta(G)\). R.P. Gupta proved two interesting results: 1) A bipartite graph \(G\) has a 5-edge-coloring in which all 6 colors appear at each vertex. 2) If \(G\) is a simple graph with \(\delta(G) > 1\), then \(G\) has a \((\delta – 1)\)-edge-coloring in which all \((\delta – 1)\) colors appear at each vertex. Let \(t\) be a positive integer. In this paper, we extend the first result by showing that for every bipartite graph, there exists a \(t\)-edge coloring such that at each vertex \(v\), \(\min\{t, d(v)\}\) colors appear. Additionally, we demonstrate that if \(G\) is a graph, then the edges of \(G\) can be colored using \(t\) colors, where for each vertex \(v\), the number of colors appearing at \(v\) is at least \(\min\{t, d(v) – 1\}\), generalizing the second result.

The Zarankiewicz number \(z(m, n; s, t)\) is the maximum number of edges in a subgraph of \(K_{m,n}\) that does not contain \(K_{s,t}\) as a subgraph. The \emph{bipartite Ramsey number} \(b(n_1, \ldots, n_k)\) is the least positive integer \(b\) such that any coloring of the edges of \(K_{b,b}\) with \(k\) colors will result in a monochromatic copy of \(K_{n_i,n_i}\) in the \(i\)-th color, for some \(i\), \(1 \leq i \leq k\). If \(n_i = m\) for all \(i\), we denote this number by \(b_k(m)\). In this paper, we obtain the exact values of some Zarankiewicz numbers for quadrilaterals (\(s = t = 2\)), and derive new bounds for diagonal multicolor bipartite Ramsey numbers avoiding quadrilaterals. Specifically, we prove that \(b_4(2) = 19\) and establish new general lower and upper bounds on \(b_k(2)\).

Given non-negative integers \(r\), \(s\), and \(t\), an \({[r, s, t]-coloring}\) of a graph \(G = (V(G), E(G))\) is a function \(c\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k-1\}\) such that \(|c(v_i) – c(v_j)| \geq r\) for every two adjacent vertices \(v_i\), \(v_j\), \(|c(e_i) – c(e_j)| \geq s\) for every two adjacent edges \(e_i\), \(e_j\), and \(|c(v_i) – c(e_j)| \geq t\) for all pairs of incident vertices \(v_i\) and edges \(e_j\). The [\(r\), \(s\), \(t\)]-chromatic number \(\chi_{r,s,t}(G)\) is the minimum \(k\) such that \(G\) admits an [\(r\), \(s\), \(t\)]-coloring. In this paper, we examine [\(r\), \(s\), \(t\)]-chromatic numbers of fans for every positive integer \(r\), \(s\), and \(t\).

A new hemisystem of the generalized quadrangle \(\mathcal{H}(3, 49)\) admit-
ting the linear group \(PSL_2(7)\) has been found.