Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

A note on a tight lower bound for capacitated MNL-bandit assortment selection models

In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon $T$, number of items $N$ and maximum assortment capacity $K$) up to logarithmic factors. Our results close an $O\left(\sqrt{K}\right)$ gap between upper and lower regret bounds from existing works.     

Boolean functions with a simple certificate for CNF complexity

In this paper we study relationships between CNF representations of a given Boolean function $f$ and essential sets of implicates of $f$. It is known that every CNF representation and every essential set must intersect. Therefore the maximum number of pairwise disjoint essential sets of $f$ provides a lower bound on the size of any CNF representation of $f$. We are interested in functions, for which this lower bound is tight, and call such functions coverable. We prove that for every coverable function there exists a polynomially verifiable certificate (witness) for its minimum CNF size. On the other hand, we show that not all functions are coverable, and construct examples of non-coverable functions. Moreover, we prove that computing the lower bound, i.e. the maximum number of pairwise disjoint essential sets, is $NP$-hard under various restrictions on the function and on its input representation.     

Distance edge-colourings and matchings

We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd?s–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd?s–Ne?et?il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień.     

Efficient algorithms for wavelength assignment on trees of rings

A fundamental problem in communication networks is wavelength assignment (WA): given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree using at most 3L wavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L upper bound is tight since there are instances of the WA problem that require 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation (resp. 2.5-approximation) algorithm for the WA problem on a tree of rings with degree at most six (resp. eight). Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).     

Matroid Matching Via Mixed Skew-Symmetric Matrices

Tutte associates a V by V skew-symmetric matrix T, having indeterminate entries, with a graph G=(V,E). This matrix, called the Tutte matrix, has rank exactly twice the size of a maximum cardinality matching of G. Thus, to find the size of a maximum matching it suffices to compute the rank of T. We consider the more general problem of computing the rank of T + K where K is a real V by V skew-symmetric matrix. This modest generalization of the matching problem contains the linear matroid matching problem and, more generally, the linear delta-matroid parity problem. We present a tight upper bound on the rank of T + K by decomposing T + K into a sum of matrices whose ranks are easy to compute.Part of this research was done while the authors visited the Fields Institute in Toronto, Canada. The research was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

On complexity of special maximum matchings constructing

For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper) bound for the cardinality of its maximum matching.     

A study on oriented relative clique number

An oriented graph is a directed graph with no directed cycle of length one or two. The relative clique number of an oriented graph is the cardinality of a largest subset $X$ of vertices such that each pair of vertices is either adjacent or connected by a directed 2-path. It is known that the oriented relative clique number of a planar graph is at most 80. Here we improve the upper bound to 32. We also prove an upper bound of 14 for oriented relative clique number of triangle-free planar graphs. Furthermore, we determine the exact values of oriented relative clique number for the families of outerplanar graphs with girth at least $g$ and planar graphs with girth at least $g+2$ for all $g\ge 3$. Moreover, we study the relation of oriented relative clique number with oriented chromatic number, oriented absolute clique number and maximum degree of a graph. We also show that oriented relative clique number of a connected subcubic graph is at most seven which weakly supports a conjecture by Sopena (JGT 1997).     

Optimal on-line colorings for minimizing the number of ADMs in optical networks

We consider the problem of minimizing the number of ADMs in optical networks. All previous theoretical studies of this problem dealt with the off-line case, where all the lightpaths are given in advance. In a real-life situation, the requests (lightpaths) arrive at the network on-line, and we have to assign them wavelengths so as to minimize the switching cost. This study is thus of great importance in the theory of optical networks. We present a deterministic on-line algorithm for the problem, and show its competitive ratio to be $\frac{7}{4}$. We show that this result is best possible in general. Moreover, we show that even for the ring topology network there is no on-line algorithm with competitive ratio better than $\frac{7}{4}$. We show that on path topology the competitive ratio of the algorithm is $\frac{3}{2}$. This is optimal for in this topology. The lower bound on ring topology does not hold when the ring is of bounded size. We analyze the triangle topology and show a tight bound of $\frac{5}{3}$ for it. The analyses of the upper bounds, as well as those for the lower bounds, are all using a variety of proof techniques, which are of interest by their own, and which might prove helpful in future research on the topic.     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.     

给定最大匹配数的树的零阶广义Randid(c)指标

图G的零阶广义Randi指标定义为0Rα（G）=v∈V（G）d（v）α,其中d（v）为图G的顶点v的度,α为任意实数.研究了树的零阶广义Rα指标的极值问题,利用分析和图的理论,确定了任意给定最大匹配数的树的最大和最小Rα的值,并刻画了达到该极值的树.     

On edge-disjoint pairs of matchings

For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for |M|/|H|.     

Cyclic degree and cyclic coloring of 3-polytopes

A vertex coloring of a plane graph is called cyclic if the vertices in each face bounding cycle are colored differently. The main result is an improvement of the upper bound for the cyclic chromatic number of 3-polytopes due to Plummer and Toft, 1987 (J. Graph Theory 11 (1987) 505–517). The proof is based on a structural property of 3-polytopes, in a sense stronger than that implied by Lebesgue's theorem of 1940. Namely, precise upper bound is obtained for the minimum cyclic degree of 3-polytopes with the maximum face size at least 24. © 1996 John Wiley & Sons, Inc.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.