BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
A graph is (d1,...,dr)-colorable if its vertex set can be partitioned into r sets V1,...,Vr so that the maximum degree of the graph induced by Vi is at most di for each i∈{1,...,r}. For a given pair (g,d1), the question of determining the minimum d2=d2(g;d1) such that planar graphs with girth at least g are (d1,d2)-colorable has attracted much interest. The finiteness of d2(g;d1) was known for all cases except when (g,d1)=(5,1). Montassier and Ochem explicitly asked if d2(5;1) is finite. We answer this question in the affirmative with d2(5;1)≤10; namely, we prove that all planar graphs with girth at least 5 are (1,10)-colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K=K(γ) where graphs with girth at least 5 that are embeddable on S are (1,K)-colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least 5 are (0,k)-colorable.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.