Generalizations of Graham’s pebbling conjecture

We investigate generalizations of pebbling numbers and of Graham’s pebbling conjecture that $\pi \left(G\square H\right)\le \pi \left(G\right)\pi \left(H\right)$, where $\pi \left(G\right)$ is the pebbling number of the graph $G$. We develop new machinery to attack the conjecture, which is now twenty years old. We show that certain conjectures imply others that initially appear stronger. We also find counterexamples that shows that Sjöstrand’s theorem on cover pebbling does not apply if we allow the cost of transferring a pebble from one vertex to an adjacent vertex to depend on the weight of the edge and we describe an alternate pebbling number for which Graham’s conjecture is demonstrably false.     

Gal’s conjecture for nestohedra corresponding to complete bipartite graphs

Convex polytopes have interested mathematicians since very ancient times. At present, they occupy a central place in convex geometry, combinatorics, and toric topology and demonstrate the harmony and beauty of mathematics. This paper considers the problem of describing the f-vectors of simple flag polytopes, that is, simple polytopes in which any set of pairwise intersecting facets has nonempty intersection. We show that for each nestohedron corresponding to a connected building set, the h-polynomial is a descent-generating function for some class of permutations; we also prove Gal’s conjecture on the nonnegativity of γ-vectors of flag polytopes for nestohedra constructed over complete bipartite graphs.     

The proof of Ushio''''s conjecture concerning path factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint Pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of Pv-factorization of Km,n. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio's conjecture is true when v = 4k-1. In this paper we shall show that Ushio Conjecture is true when v = 4k 1, and then Ushio's conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P4k 1-factorization of Km,n is (i) 2km≤ (2k 1)n, (ii) 2kn≤ (2k 1)m, (iii) m n = 0 (mod 4k 1), (iv) (4k 1)mn/[4k(m n)] is an integer.     

Hadwiger’s conjecture for uncountable graphs

We consider the infinite form of Hadwiger’s conjecture. We give a(n apparently novel) proof of Halin’s 1967 theorem stating that every graph X with coloring number \(>\kappa \) (specifically with chromatic number \(>\kappa \)) contains a subdivision of \(K_\kappa \). We also prove that there is a graph of cardinality \(2^\kappa \) and chromatic number \(\kappa ^+\) which does not contain \(K_{\kappa ^+}\) as a minor. Further, it is consistent that every graph of size and chromatic number \(\aleph _1\) contains a subdivision of \(K_{\aleph _1}\).     

The bondage number of graphs on topological surfaces and Teschner’s conjecture

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner’s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.     

Decomposition of cubic graphs related to Wegner’s conjecture

Thomassen formulated the following conjecture: Every 3-connected cubic graph has a red–blue vertex coloring such that the blue subgraph has maximum degree 1 (that is, it consists of a matching and some isolated vertices) and the red subgraph has minimum degree at least 1 and contains no 3-edge path. We prove the conjecture for Generalized Petersen graphs.We indicate that a coloring with the same properties might exist for any subcubic graph. We confirm this statement for all subcubic trees.     

A sufficient condition for Kim’s conjecture on the competition numbers of graphs

A hole of a graph $G$ is an induced cycle of length at least 4. Kim (2005) [3] conjectured that the competition number $k\left(G\right)$ is bounded by $h\left(G\right)+1$ for any graph $G$, where $h\left(G\right)$ is the number of holes of $G$. Li and Chang (2009) [5] proved that the conjecture is true for a graph whose holes all satisfy a property called ‘independence’. In this paper, by using similar proof techniques in Li and Chang (2009) [5], we prove the conjecture for graphs satisfying two conditions that allow the holes to overlap a lot.     

P_(4k-1)-factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of Pv-factorization of Km,n.When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of Km,n is (1) (2k - 1)m ≤ 2kn, (2) (2k -1)n≤2km, (3) m n ≡ 0 (mod 4k - 1), (4) (4k -1)mn/[2(2k -1)(m n)] is an integer.     

Proof of Ding’s conjecture on maximal stable sets and maximal cliques in planar graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.     

Remarks on Harada’s conjecture

An open conjecture by Harada from 1981 gives an easy characterization of the p-blocks of a finite group in terms of the ordinary character table. Kiyota and Okuyama have shown that the conjecture holds for p-solvable groups. In the present work we extend this result using a criterion on the decomposition matrix. In this way we prove Harada’s Conjecture for several new families of defect groups and for all blocks of sporadic simple groups. In the second part of the paper we present a dual approach to Harada’s Conjecture.     

Topological minors in line graphs — A proof of Zha’s conjecture

In 1992, Xiaoya Zha conjectured that the line graph of a 3-connected non-planar graph contains a subdivision of K ₅. In this paper we prove this conjecture. This result is the main ingredient of [4] where a complete characterization of all the 4-connected claw-free graphs not containing a subdivision of K ₅ is obtained.     

A remark on Donovan’s conjecture

It is shown that the difference between Donovans conjecture and the weaker conjecture bounding Cartan numbers of blocks of finite groups by the defect of the blocks can be expressed in terms of the relationship between pairs of Galois conjugate blocks. A consequence is that for principal blocks the two conjectures are equivalent.Received: 11 August 2003     

Domination in the hierarchical product and Vizing’s conjecture

Given a graph $G$, a set $S?V\left(G\right)$ is a dominating set of $G$ if every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The domination number of $G$, denoted $\gamma \left(G\right)$, is the minimum cardinality of a dominating set of $G$. Vizing’s conjecture states that $\gamma (G\square H)\ge \gamma \left(G\right)\gamma \left(H\right)$ for any graphs $G$ and $H$ where $G\square H$ denotes the Cartesian product of $G$ and $H$. In this paper, we continue the work by Anderson et al. (2016) by studying the domination number of the hierarchical product. Specifically, we show that partitioning the vertex set of a graph in a particular way shows a trend in the lower bound of the domination number of the product, providing further evidence that the conjecture is true.     

Remarks on Serre’s modularity conjecture

In this article we give a proof of Serre’s conjecture for the case of odd level and arbitrary weight. Our proof does not use any modularity lifting theorem in characteristic 2 (moreover, we will not consider at all characteristic 2 representations at any step of our proof). The key tool in the proof is a very general modularity lifting result of Kisin, which is combined with the methods and results of previous articles on Serre’s conjecture by Khare, Wintenberger, and the author, and modularity results of Schoof for abelian varieties of small conductor. Assuming GRH, infinitely many cases of even level will also be proved.     

Exceptional cases of Terai’s conjecture on Diophantine equations

Let a, b, c be relatively prime positive integers such that a ^p  + b ^q  = c ^r for fixed integers p, q, r ≥ 2. Terai conjectured that the equation a ^x  + b ^y  = c ^z in positive integers has only the solution (x, y, z) = (p, q, r) except for specific cases. In this paper, we consider the case q = r = 2 and give some results related to exceptional cases.     

A note on Barnette’s conjecture

A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring.A Barnette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.