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
Given a graph G, a decomposition of G is a partition of its edges. A graph is (d,h)-decomposable if its edge set can be partitioned into a d-degenerate graph and a graph with maximum degree at most h. For d≤4, we are interested in the minimum integer hd such that every planar graph is (d,hd)-decomposable. It was known that h3≤4, h2≤8, and h1=∞. This paper proves that h4=1,h3=2, and 4≤h2≤6.
This paper disproves a conjecture of Wang, Wu, Yan and Xie, and answers in negative a question in Dvorak, Pekarek and Sereni. In return, we pose five open problems.
Given a graph G, the strong clique number of G, denoted ωS(G), is the maximum size of a set S of edges such that every pair of edges in S has distance at most 2 in the line graph of G. As a relaxation of the renowned Erdős--Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if G is a C2k-free graph, then ωS(G)≤(2k−1)Δ(G)−(22k−1), and if G is a C2k-free bipartite graph, then ωS(G)≤kΔ(G)−(k−1). We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a {C5,C2k}-free graph G with Δ(G)≥1 satisfies ωS(G)≤kΔ(G)−(k−1), when either k≥4 or k∈{2,3} and G is also C3-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for k≥3, we prove that a C2k-free graph G with Δ(G)≥1 satisfies ωS(G)≤(2k−1)Δ(G)+(2k−1)2. This improves some results of Cames van Batenburg, Kang, and Pirot.
Given a graph G possibly with multiple edges but no loops, denote by Δ the {\it maximum degree}, μ the {\it multiplicity}, χ′ the {\it chromatic index} and χf′ the {\it fractional chromatic index} of G, respectively. It is known that Δ≤χf′≤χ′≤Δ+μ, where the upper bound is a classic result of Vizing. While deciding the exact value of χ′ is a classic NP-complete problem, the computing of χf′ is in polynomial time. In fact, it is shown that if χf′>Δ then χf′=max⌊∣V(H)∣/2⌋∣E(H)∣, where the maximality is over all induced subgraphs H of G. Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that χ′=⌈χf′⌉ if χ′≥Δ+2, which is commonly referred as Goldberg's conjecture. In this paper, we show that if χ′>Δ+3Δ/2 then χ′=⌈χf′⌉. The previous best known result is for graphs with χ′>Δ+Δ/2 obtained by Scheide, and by Chen, Yu and Zang, independently. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: {\it For any positive integer m with m≥3, every graph G with χ′>m−1mΔ+m−1m−3 satisfies χ′=⌈χf′⌉.} Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We show that it is true for m≤23. Moreover, we show that Goldberg's conjecture holds for graphs G with Δ≤23 or ∣V(G)∣≤23.
Let k and ℓ be positive integers. A cycle with two blocks c(k,ℓ) is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomassé (2007) asked if, given positive integers k and ℓ such that k+ℓ≥4, any strongly connected digraph D containing no c(k,ℓ) has chromatic number at most k+ℓ−1. In this paper, we show that such digraph D has chromatic number at most O((k+ℓ)2), improving the previous upper bound O((k+ℓ)4) obtained by Cohen, Havet, Lochet and Nisse (2016). In fact, we are able to find a digraph which shows that the answer to the above problem is no. We also show that if in addition D is Hamiltonian, then its underlying simple graph is (k+ℓ−1)-degenerate and thus the chromatic number of D is at most k+ℓ, which is tight.
For a graph G and a tree-decomposition (T,B) of G, the chromatic number of (T,B) is the maximum of χ(G[B]), taken over all bags B∈B. The tree-chromatic number of G is the minimum chromatic number of all tree-decompositions (T,B) of G. The path-chromatic number of G is defined analogously. In this paper, we introduce an operation that always increases the path-chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path-chromatic number and tree-chromatic number are different. This settles a question of Seymour. Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded.
A homogeneous set of an n-vertex graph is a set X of vertices (2≤∣X∣≤n−1) such that every vertex not in X is either complete or anticomplete to X. A graph is called prime if it has no homogeneous set. A chain of length t is a sequence of t+1 vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all n, there exists N such that every prime graph with at least N vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from K1,n by subdividing every edge once, (2) the line graph of K2,n, (3) the line graph of the graph in (1), (4) the half-graph of height n, (5) a prime graph induced by a chain of length n, (6) two particular graphs obtained from the half-graph of height n by making one side a clique and adding one vertex.
A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths. We conjecture that when k = 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins. We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.
A finite tree T with ∣V(T)∣≥2 is called {\it automorphism-free} if there is no non-trivial automorphism of T. Let AFT be the poset with the element set of all finite automorphism-free trees (up to graph isomorphism) ordered by T1⪯T2 if T1 can be obtained from T2 by successively deleting one leaf at a time in such a way that each intermediate tree is also automorphism-free. In this paper, we prove that AFT has a unique minimal element. This result gives an affirmative answer to the question asked by Rupinski.
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.