Colouring series-parallel graphs

We establish a minimax formula for the chromatic index of series-parallel graphs; and also prove the correctness of a greedy algorithm for finding a vertex-colouring of a series-parallel graph.     

Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.     

On the Number of Latin Squares

We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004     

Nowhere-Zero 4-Flows,Simultaneous Edge-Colorings,And Critical Partial Latin Squares

It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.     

Asymmetric marking games on line graphs

This paper investigates the asymmetric marking games on line graphs. Suppose G is a graph with maximum degree Δ and G has an orientation with maximum outdegree k, we show that the (a,1)-game coloring number of the line graph of G is at most . When a=1, this improves some known results of the game coloring number of the line graphs.     

The inertia set of the join of graphs

Let G=(V,E) be a graph with V={1,2,…,n}. Denote by S(G) the set of all real symmetric n×n matrices A=[a_i,j] with a_i,j≠0, i≠j if and only if ij is an edge of G. Denote by I^↗(G) the set of all pairs (p,q) of natural numbers such that there exists a matrix A∈S(G) with at most p positive and q negative eigenvalues. We show that if G is the join of G₁ and G₂, then I^↗(G)?{(1,1)}=I^↗(G₁∨K₁)∩I^↗(G₂∨K₁)?{(1,1)}. Further, we show that if G is a graph with s isolated vertices, then , where denotes the graph obtained from G be removing all isolated vertices, and we give a combinatorial characterization of graphs G with (1,1)∈I^↗(G). We use these results to determine I^↗(G) for every complete multipartite graph G.     

Holey self-orthogonal Latin squares with symmetric orthogonal mates

We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh ⁿ are also sufficient with at most 28 pairs (h, n) of possible exceptions. Research supported in part by NSERC Grant A-5320 for the first author, NSF Grants CCR-9504205 and CCR-9357851 for the second author, and NSFC Grant 19231060-2 for the third author.     

Lie algebras and the Four Color Theorem

We present a statement about Lie algebras that is equivalent to the Four Color Theorem.     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

On pallets for Fox colorings of spatial graphs

We introduce the notion of pallets of quandles and define coloring invariants for spatial graphs which give a generalization of Fox colorings studied in Ishii and Yasuhara (1997) [4]. All pallets for dihedral quandles are obtained from the quotient sets of the universal pallets under a certain equivalence relation. We study the quotient sets and classify their elements.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Hom complexes and hypergraph colorings

Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes.     

On the genus of real projective spaces

We construct a crystallization of the real projective space whose associated contracted complex is minimal with respect to the number of n-simplexes. Then we compute the regular genus of , which is the minimum genus of a closed connected surface into which a crystallization of regularly embeds. Received: 7 February 2007     

Imperfect and Nonideal Clutters: A Common Approach

We prove three theorems. First, Lovászs theorem about minimal imperfect clutters, including also Padbergs corollaries. Second, Lehmans result on minimal nonideal clutters. Third, a common generalization of these two. The endeavor of working out a common denominator for Lovászs and Lehmans theorems leads, besides the common generalization, to a better understanding and simple polyhedral proofs of both.* Visiting of the French Ministry of Research and Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April 1996.     

Zero forcing parameters and minimum rank problems

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z₊(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.     

Computing the genus of the 2-amalgamations of graphs

The above authors [2] and S. Stahl [3] have shown that if a graphG is the 2-amalgamation of subgraphsG ₁ andG ₂ (namely ifG=G ₁∪G ₂ andG ₁∩G ₂={x, y}, two distinct points) then the orientable genus ofG,γ(G), is given byγ(G)=γ(G ₁)+γ(G ₂)+ε, whereε=0,1 or −1. In this paper we sharpen that result by giving a means by whichε may be computed exactly. This result is then used to give two irreducible graphs for each orientable surface.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

A characterization of planar graphs by trémaux orders

A new characterization of planar graphs is stated in terms of an order relation on the vertices, called the Trémaux order, associated with any Trémaux spanning tree or Depth-First-Search Tree. The proof relies on the work of W. T. Tutte on the theory of crossings and the Trémaux algebraic theory of planarity developed by P. Rosenstiehl.