Kaibel, Volker Lee, Jon Walter, Matthias Weltge, Stefan
Published in
Graphs and Combinatorics

We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s deco...

Krotov, Denis S. Bespalov, Evgeny A.
Published in
Graphs and Combinatorics

The maximum independent sets in the Doob graphs D(m, n) are analogs of the distance-2 MDS codes in Hamming graphs and of the latin hypercubes. We prove the characterization of these sets stating that every such set is semilinear or reducible. As related objects, we study vertex sets with maximum cut (edge boundary) in D(m, n) and prove some facts o...

Wang, Ruixia
Published in
Graphs and Combinatorics

Kernel is an important topic in digraphs. A digraph such that every proper induced subdigraph has a kernel is said to be critical kernel imperfect (CKI, for short) if the digraph does not have a kernel. Galeana-Sánchez and Olsen characterized the CKI-digraphs for the following families of digraphs: asymmetric arc-locally in-/out-semicomplete digrap...

Liu, Shunyi
Published in
Graphs and Combinatorics

Let G be a graph, and let L(G) and Q(G) denote respectively the Laplacian matrix and the signless Laplacian matrix of G. The Laplacian (respectively, signless Laplacian) permanental polynomial of G is defined as the permanent of the characteristic matrix of L(G) (respectively, Q(G)). In this paper, we give combinatorial expressions for the first fi...

Aharoni, Ron Gorelik, Irina
Published in
Graphs and Combinatorics

The independent domination numberγi(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma ^i(G)$$\end{document} of a graph G is the maximum, over all independent set...

Kim, Seog-Jin Yu, Xiaowei
Published in
Graphs and Combinatorics

DP-coloring (also known as correspondence coloring) of a simple graph is a generalization of list coloring. It is known that planar graphs without 4-cycles adjacent to triangles are 4-choosable, and planar graphs without 4-cycles are DP-4-colorable. In this paper, we show that planar graphs without 4-cycles adjacent to triangles are DP-4-colorable,...

Salia, Nika Tompkins, Casey Zamora, Oscar
Published in
Graphs and Combinatorics

While investigating odd-cycle free hypergraphs, Győri and Lemons introduced a colored version of the classical theorem of Erdős and Gallai on Pk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-...

Hahn, Marvin Anas
Published in
Graphs and Combinatorics

Hurwitz numbers count genus g, degree d covers of the complex projective line with fixed branched locus and fixed ramification data. An equivalent description is given by factorisations in the symmetric group. Simple double Hurwitz numbers are a class of Hurwitz-type counts of specific interest. In recent years a related counting problem in the con...

Wu, Yaokun Xiong, Yanzhen Zaw, Soesoe
Published in
Graphs and Combinatorics

Let D be a digraph. The competition graph of D is the graph sharing the same vertex set with D such that two different vertices are adjacent if and only if they have a common out-neighbor in D; the phylogeny graph of D is the competition graph of the digraph obtained from D by adding a loop at every vertex. For any graph G with n vertices, its comp...

Zhang, Xin Niu, Bei Yu, Jiguo
Published in
Graphs and Combinatorics

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. In this paper, we first give a useful structural theorem for 1-planar graphs, and then apply it to the list edge and list total coloring, the (p, 1)-total labelling, and the equitable edge coloring of 1-planar graphs. More precisely, we verify ...