Explore the vast range of titles available.

For a graphGand an integerk≥ 2 , aχ'_(k) -coloring ofGis an edge coloring ofGsuch that the subgraph induced by the edges of each color has all degrees congruent to1 (\\mod k) , andχ'_(k)(G)is the minimum number of colors in aχ'_(k) -coloring ofG . In [\"The modkchromatic index of graphs isO(k) \", J. Graph Theory. 2023; 102: 197-200], Botler, Colucci and Kohayakawa proved thatχ'_(k)(G)≤ 198k-101for every graphG . In this paper, we show thatχ'_(k)(G) ≤ 177k-93 .

For the given bipartite graphsG₁,G₂,…,G_(t) , the multicolor bipartite Ramsey numberBR(G₁,G₂,…,G_(t))is the smallest positive integerbsuch that anyt -edge-coloring ofK_(b,b)contains a monochromatic subgraph isomorphic toGᵢ , colored with thei th color for some1≤ i≤ t . We compute the exact values of the bipartite Ramsey numbersBR(C₈,C_(2n))forn≥2 .

We establish exact values for the2 -limited broadcast domination number of various grid graphs, in particularC_(m)□ C_(n)for3 ≤ m ≤ 6and alln≥ m ,P_(m) □ C₃for allm ≥ 3 , andP_(m) □ C_(n)for4≤ m ≤ 5and alln ≥ m . We also produce periodically optimal values forP_(m) □ C₄andP_(m) □ C₆form ≥ 3 ,P₄ □ P_(n)forn ≥ 4 , andP₅ □ P_(n)forn ≥ 5 . Our method completes an exhaustive case analysis and eliminates cases by combining tools from linear programming with various mathematical proof techniques.

In this article we present theoretical and computational results on the existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs. We also describe an efficient algorithm to compute all polyhedral embeddings of a given cubic graph and constructions for cubic graphs with some special properties of their polyhedral embeddings. Some key results are that even cubic graphs with a polyhedral embedding on the torus can also have polyhedral embeddings in arbitrarily high genus, in fact in a genus close to the theoretical maximum for that number of vertices, and that there is no bound on the number of genera in which a cubic graph can have a polyhedral embedding. While these results suggest a large variety of polyhedral embeddings, computations for up to 28 vertices suggest that by far most of the cubic graphs do not have a polyhedral embedding in any genus and that the ratio of these graphs is increasing with the number of vertices.

The forbidden number$\\mathrm{forb}(m,F)$ , which denotes the maximum number of unique columns in an$m$ -rowed$(0,1)$ -matrix with no submatrix that is a row and column permutation of$F$ , has been widely studied in extremal set theory. Recently, this function was extended to$r$ -matrices, whose entries lie in$\\{0,1,\\dots,r-1\\}$ . The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many$(0,1)$ -matrices$F$ , including all$2$ -rowed matrices when$r > 3$ . We also prove a stability result for the$2\\times 2$identity matrix. Along the way, we expose some interesting qualitative differences between the cases$r=2$ ,$r = 3$ , and$r > 3$ .

Let$G$be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and make conjectures for the extremal triangulations and quadrangulations based on computational evidence. If$\\overline{\\sigma}(v)$denotes the arithmetic mean of the distances from$v$to all other vertices of$G$ , then the remoteness of$G$is defined as the largest value of$\\overline{\\sigma}(v)$over all vertices$v$of$G$ . We give sharp upper bounds on the remoteness of simple triangulations and quadrangulations of given order and connectivity.

Matching problems with preferences are all around us: they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists. In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. The importance of the research area was recognised in 2012 through the award of the Nobel Prize in Economic Sciences to Alvin Roth and Lloyd Shapley.

We provide a pair of ribbon graphs that have the same rotor routing and Bernardi sandpile torsors, but different topological genus. This resolves a question posed by M. Chan [Cha]. We also show that if we are given a graph, but not its ribbon structure, along with the rotor routing sandpile torsors, we are able to determine the ribbon graph's genus.

The study of geometric hypergraphs gave rise to the notion ofABAB -free hypergraphs. A hypergraph𝓗is calledABAB -free if there is an ordering of its vertices such that there are no hyperedgesA,Band verticesv₁,v₂,v₃,v₄in this order satisfyingv₁,v₃∈ A∖ Bandv₂,v₄∈ B∖ A . In this paper, we prove that it is NP-complete to decide if a hypergraph isABAB -free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such asABABA -free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete.

In a generalized Turán problem, two graphs$H$and$F$are given and the question is the maximum number of copies of$H$in an$F$ -free graph of order$n$ . In this paper, we study the number of double stars$S_{k,l}$in triangle-free graphs. We also study an opposite version of this question: what is the maximum number edges/triangles in graphs with double star type restrictions, which leads us to study two questions related to the extremal number of triangles or edges in graphs with degree-sum constraints over adjacent or non-adjacent vertices.