Chromatic number for a generalization of Cartesian product graphs.
The edge-count criterion for graphic lists.
Tree-thickness and caterpillar-thickness under girth constraints.
Independence number of 2-factor-plus-triangles graphs.
Repetition number of graphs.
Graphic and protographic lists of integers.
Acyclic sets in -majority tournaments.
Rainbow matching in edge-colored graphs.
A proof of the two-path conjecture.
On-line Ramsey theory for bounded degree graphs.
Chvátal's Condition cannot hold for both a graph and its complement
Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that or . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.
Triangle-free planar graphs with minimum degree 3 have radius at least 3
We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.
A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected
We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.
The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs
The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...
The leafage of a chordal graph
The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal...
Page 1