Explore the vast range of titles available.

For a graph G and a family of graphs$\\mathcal {F}$, the Turán number${\\mathrm {ex}}(G,\\mathcal {F})$is the maximum number of edges an$\\mathcal {F}$-free subgraph of G can have. We prove that${\\mathrm {ex}}(G,\\mathcal {F})\\ge {\\mathrm {ex}}(K_r, \\mathcal {F})$if the chromatic number of G is r and$\\mathcal {F}$is a family of connected graphs. This result answers a question raised by Briggs and Cox [‘Inverting the Turán problem’, Discrete Math. 342 (7) (2019), 1865–1884] about the inverse Turán number for all connected graphs.

We determine irregular set chromatic number of comb, friendship, K-ary tree, n-sunlet, coconut tree and jelly fish graph.

A graph$G$is equitably$k$ -choosable if, for any given$k$ -uniform list assignment$L$ ,$G$is$L$ -colorable and each color appears on at most$\\lceil\\frac{|V(G)|}{k}\\rceil$vertices. A graph is equitably$k$ -colorable if the vertex set$V(G)$can be partitioned into$k$independent subsets$V_1$ ,$V_2$ ,$\\cdots$ ,$V_k$such that$||V_i|-|V_j||\\leq 1$for$1\\leq i, j\\leq k$ . In this paper, we prove that if$G$is a planar graph without chordal$4$ - and$6$ -cycles, then$G$is equitably$k$ -colorable and equitably$k$ -choosable where$k\\geq\\max\\{\\Delta(G), 7\\}$ . Comment: 21 pages,3 figures

An antimagic labelling of a graph$G$is a bijection$f:E(G)\\to\\{1,\\ldots,E(G)\\}$such that the sums$S_v=\\sum_{e\\ni v}f(e)$distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1994) is that every connected graph other than$K_2$admits an antimagic labelling. Recently, two sets of authors (Arumugam, Premalatha, Baca \\& Semanicová-Fenovcíková (2017), and Bensmail, Senhaji \\& Lyngsie (2017)) independently introduced the weaker notion of a local antimagic labelling, where only adjacent vertices must be distinguished. Both sets of authors conjectured that any connected graph other than$K_2$admits a local antimagic labelling. We prove this latter conjecture using the probabilistic method. Thus the parameter of local antimagic chromatic number, introduced by Arumugam et al., is well-defined for every connected graph other than$K_2$. Comment: Final version for publication in DMTCS. Changes from previous version are formatting to journal style and correction of two minor typographical errors

In 2020 Bang-Jensen et. al. generalized the Haj\\'os join of two graphs to the class of digraphs and generalized several results for vertex colorings in digraphs. Although, as a consequence of these results, a digraph can be obtained by Haj\\'os constructions (directed Haj\\'os join and identifying non-adjacent vertices), determining the Haj\\'os constructions to obtain the digraph is a complex problem. In particular, Bang-Jensen et al. posed the problem of determining the Haj\\'os operations to construct the symmetric 5-cycle from the complete symmetric digraph of order 3 using only Haj\\'os constructions. We successfully adapted a rank-based genetic algorithm to solve this problem by the introduction of innovative recombination and mutation operators from graph theory. The Haj\\'os Join became the recombination operator and the identification of independent vertices became the mutation operator. In this way, we were able to obtain a sequence of only 16 Haj\\'os operations to construct the symmetric cycle of order 5.

A path of a vertex-colored graph is conflict-free path, if there exists a color used only on one of its vertices; a vertex-colored graph is conflict-free vertex-connected, if there is a conflict-free path between each pair of distinct vertices of the graph. For a connected graph G, the minimum number of colors required to make G conflict-free vertex-connected is conflict-free vertex- connection number of G, denoted by vcfc(G). In this paper, we first showed an upper bound of vcfc(G) for the general graph by structural method. And then, we gave a partial solution to the conjecture on the conflict-free vertex-connection number by contradiction, posed by Doan and Schiermeyer in [Conflict-free vertex connection number at most 3 and size of graphs, Discus. Math. Graph Theory].

We prove that the family of graphs containing no cycle with exactly k -chords is$\\chi $-bounded, for k large enough or of form$\\ell (\\ell -2)$with$\\ell \\ge 3$an integer. This verifies (up to a finite number of values k ) a conjecture of Aboulker and Bousquet (2015).

A graph$G$is said to be an$(s, k)$ -polar graph if its vertex set admits a partition$(A, B)$such that$A$and$B$induce, respectively, a complete$s$ -partite graph and the disjoint union of at most$k$complete graphs. Polar graphs and monopolar graphs are defined as$(\\infty, \\infty)$ - and$(1, \\infty)$ -polar graphs, respectively, and unipolar graphs are those graphs with a polar partition$(A, B)$such that$A$is a clique. The problems of deciding whether an arbitrary graph is a polar graph or a monopolar graph are known to be NP-complete. In contrast, deciding whether a graph is a unipolar graph can be done in polynomial time. In this work we prove that the three previous problems can be solved in linear time on the classes of$P_4$ -sparse and$P_4$ -extendible graphs, generalizing analogous results previously known for cographs. Additionally, we provide finite forbidden subgraph characterizations for$(2,2)$ -polar graphs on$P_4$ -sparse and$P_4$ -extendible graphs, also generalizing analogous results recently obtained for the class of cographs.

The Borodin–Kostochka Conjecture states that for a graph G , if Δ ( G ) ≥ 9 , then χ ( G ) ≤ max { Δ ( G ) - 1 , ω ( G ) } . In this paper, we prove the Borodin–Kostochka Conjecture holding for odd-hole-free graphs.