Search

Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n+1)/3, and described an infinite class of tight examples. We show that all n-vertex planar triangle-free graphs except for this one infinite class have independent sets of size at least (n+2)/3.

Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G is triangle-free and all lists have size at least four, then there exists an L-coloring respecting at least a constant fraction of the preferences., Comment: 28 pages, 5 figures

Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at least three, then there exists an L-coloring respecting at least a constant fraction of the preferences., Comment: 11 pages, no figures. arXiv admin note: text overlap with arXiv:1902.02971

We show that an Eulerian triangulation of the Klein bottle has chromatic number equal to six if and only if it contains a complete graph of order six, and it is 5-colorable, otherwise. As a consequence of our proof, we derive that every Eulerian triangulation of the Klein bottle with face-width at least four is 5-colorable.

For a given number L , an L -length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s - t -path of length at most L remains in the graph after removing the edges (nodes, respectively) in C . An L -length-bounded flow is a flow that can be decomposed into flow paths of length at most L . In contrast to classical flow theory, we describe instances for which the minimum L -length-bounded edge-cut (node-cut, respectively) is Θ( n 2/3 )-times (Θ(√ n )-times, respectively) larger than the maximum L -length-bounded flow, where n denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is NP -hard to approximate within a factor of 1.1377 for L ≥ 5 in the case of node-cuts and for L ≥ 4 in the case of edge-cuts. We also describe algorithms with approximation ratio O (min{ L , n/L }) ⊆ O √ n in the node case and O (min { L , n 2 / L 2 ,√ m } ⊆ O 2/3 in the edge case, where m denotes the number of edges. Concerning L -length-bounded flows, we show that in graphs with unit-capacities and general edge lengths it is NP -complete to decide whether there is a fractional length-bounded flow of a given value. We analyze the structure of optimal solutions and present further complexity results.

Given a graph G=(V,E), two fixed vertices s,[email protected]?V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs. We write [email protected]?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)@?F we have [email protected]?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)@?F satisfy [email protected]?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)@?F satisfy [email protected][email protected][email protected]?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.

We develop an idea of a local 3-edge-coloring of a cubic graph, a generalization of the usual 3-edge-coloring. We allow for an unlimited number of colors but require that the colors of two edges meeting at a vertex always determine the same third color. Local 3-edge-colorings are described in terms of colorings by points of a partial Steiner triple system such that the colors meeting at each vertex form a triple of the system. An important place in our investigation is held by the two smallest non-trivial Steiner triple systems, the Fano plane PG(2,2) and the affine plane AG(2,3). For i=4,5, and 6 we identify certain configurations Fi and Ai of i lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an Fi-coloring if and only if it admits an Ai-coloring.Among consequences of this is the result of Holroyd and Škoviera [F. Holroyd, M. Škoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57–66] that the edges of every bridgeless cubic graph can be colored by using points and blocks of any non-trivial Steiner triple system S. Another consequence is that every bridgeless cubic graph has a proper edge-coloring by elements of any abelian group of order at least 12 such that around each vertex the group elements sum to 0.We also propose several conjectures concerning edge-coloring of cubic graphs and relate them to several well-known conjectures. In particular, we show that both the Cycle Double Cover Conjecture and the Fulkerson Conjecture can be formulated as a coloring problem in terms of known geometric configurations — the Desargues configuration and the Cremona–Richmond configuration, respectively.

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set Π of constraint types, ρl(Π) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from Π. In the case of sets Π consisting of finitely many Boolean predicates, we express the limit ρ∞(Π):=liml→∞ρl(Π) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set Π) running in time linear in the size of the input and 1/ε which finds either an inconsistent set of constraints (of size bounded by the function of ε) or a truth assignment which satisfies the fraction of at least ρ∞(Π)-ε of the given constraints. We also compute the values of ρl({P}) for several specific predicates P.

Let Ω ⊂ R N be a bounded open set and let g : Ω × R → R be a Caratheodory function that satisfies standard growth conditions. Then the functional Φ ( u ) = ∫ Ω g ( x , u ( x ) ) d x is weakly continuous on W 0 1 , p ( Ω ) , 1 ≤ p ≤ ∞ , if and only if g is linear in the second variable.

We show the number of triangles of G"n","1"/"2 is almost uniformly distributed among residue classes modulo q, where q is a prime number bounded by @Q(logn). This implies a consequence of a conjecture of Bollobas, Pebody and Riordan (that almost every random graph G"n","1"/"2 is uniquely determined by its Tutte polynomial): almost every pair of independently chosen random graphs G"n","1"/"2 has different Tutte polynomials.

International audience; We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948-2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.

Markov width of a graph is a graph invariant defined as the maximum degree of a Markov basis element for the corresponding graph model for binary contingency tables. We show that a graph has Markov width at most four if and only if it contains no $K_4$ as a minor, answering a question of Develin and Sullivant. We also present a lower bound of order $\Omega(n^{2-\varepsilon})$ on the Markov width of $K_n$.

It is conjectured that every fullerene graph is hamiltonian. Jendrol' and Owens proved [J. Math. Chem. 18 (1995), pp. 83--90] that every fullerene graph on n vertices has a cycle of length at least 4n/5. In this paper, we improve this bound to 5n/6-2/3., 12 pages, 10 figures

In this paper we study 3-dimensional visibility representations of complete graphs. The vertices are represented by equal regular polygons lying in planes parallel to the xy-plane. Two vertices are adjacent if and only if the two corresponding polygons see each other - i.e. it is possible to construct an abscissa perpendicular to the xy-plane connecting the two polygons and avoiding all the others.

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set Π of constraint types, ρl(Π) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints from the set Π. We study the asymptotic behavior of ρl(Π) for sets Π consisting of Boolean predicates.

For two bipartite graphs $G$ and $G'$, a bijection $\psi: E(G) \rightarrow E(G')$ is called a (perfect) matching preserver provided that $M$ is a perfect matching in $G$ if and only if $\psi(M)$ is a perfect matching in $G'$. We characterize bipartite graphs $G$ and $G'$ which are related by a matching preserver and the matching preservers between them.

The cyclic edge connectivity is the size of a smallest edge cut in a graph such that at least two of the connected components contain cycles. We present an algorithm running in time O(n 2log2 n) for computing the cyclic edge connectivity of n-vertex cubic graphs.