-
Article
On Sizes of 1-Cross Intersecting Set Pair Systems
Let \( \{(A_{i},B_{i})\}_{i=1}^{m} \) be a set pair system. Füredi, Gyárfás, and Király called it
-
Article
On Differences Between DP-Coloring and List Coloring
DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle [12]. Many known upper bounds for the list-chromatic number extend to the DP-ch...
-
Chapter
An Algorithmic Answer to the Ore-Type Version of Dirac’s Question on Disjoint Cycles
Corrádi and Hajnal in 1963 proved the following theorem on the NP-complete problem on the existence of k disjoint cycles in an n-vertex graph G: For all k ≥ 1 and n ≥ 3k, every (simple) n-vertex graph G with mini...
-
Article
Sharpening an Ore-type version of the Corrádi–Hajnal theorem
Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) ...
-
Article
On DP-coloring of graphs and multigraphs
While solving a question on the list coloring of planar graphs, Dvořák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem ...
-
Article
A refinement of a result of Corrádi and Hajnal
Corrádi and Hajnal proved that for every k ≥ 1 and n ≥ 3k, every n-vertex graph with minimum degree at least 2k contains k vertex-disjoint cycles. This implies that every 3k-vertex graph with maximum degree at mo...
-
Article
Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V 1 and V 0 so that in G[V 1] every vertex has degree at mos...
-
Article
Oriented 5-coloring of sparse plane graphs
An oriented k-coloring of an oriented graph H is defined to be an oriented homomorphism of H into a k-vertex tournament. It is proved that every orientation of a graph with girth at least 5 and maximum average de...
-
Article
On Graphs With Small Ramsey Numbers, II
There exists a constant C such that for every d-degenerate graphs G 1 and G 2 on n vertices, Ramsey number R(G 1,G 2) is at most CnΔ, where Δ is the...
-
Article
Estimating the Minimal Number of Colors in Acyclic \(k \) -Strong Colorings of Maps on Surfaces
A coloring of the vertices of a graph is called acyclic if the ends of each edge are colored in distinct colors, and there are no two-colored cycles. Suppose each face of rank
-
Article
On the Number of Edges in Colour-Critical Graphs and Hypergraphs
is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at le...
-
Article
Acyclick-strong coloring of maps on surfaces
A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater thank, k ≥ 4, on a surfaceS ...
-
Article
The Dimension of Interior Levels of the Boolean Lattice, II
Extending an old lemma by Dushnik, we establish the dimension d(3, k; n) of the containment order generated by the 3-element and k-element subsets of an n-element set for most k between
-
Article
On Large Systems of Sets with No Large Weak Δ-subsystems
Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by Rödl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of ...
-
Article
The Dimension of Neighboring Levels of the Boolean Lattice
The order dimension of suborders of the Boolean lattice \(B_n \) is considered. It is shown that the suborder of ...
-
Chapter
A Bound of the Cardinality of Families not Containing Δ-Systems
P. Erdős and R. Rado defined a Δ-system as a family in which every two members have the same intersection. Here we obtain a new upper bound of the maximum cardinality φ(n) of an n-uniform family not containing an...
-
Chapter
A Refinement of the Frank-Sebő-Tardos Theorem and Its Applications
The problem of finding a T-join of minimum cardinality is studied. This problem includes the Chinese Postman Problem, the Shortest Path Problem and the Maximum Matching Problem. It is also closely related to the ...
-
Chapter
On the Length of the Chinese Postman Tour in Regular Graphs
The Chinese Postman problem, i.e., the problem of finding a shortest closed walk traversing all edges of a regular graph of an odd degree is equivalent to the problem of finding a minimum join, i.e., a spannin...
-
Chapter
On Minimum Independent Dominating Sets in Graphs
We study the question as to the extent to which the size id(G) of a minimum independent dominating set of a graph G can differ from the size d(G) of a minimum dominating set of G under some restrictions on the ve...
-
Chapter and Conference Paper
A characterization of Seymour graphs
A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T-cuts is equal to the cardinality of a minimum T-join for every even subset T of V(G). Several families of graphs h...
