Abstract Given a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in $${\mathbb R}^2$$ R 2 having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most $$\omega $$ ω that the chromatic number $$\chi (G)$$ χ ( G ) of G is at most $$d\omega $$ d ω . We show for every even value of $$\omega $$ ω how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $$\chi $$ χ -binding function of d-DIR is $$\omega \mapsto d\omega $$ ω ↦ d ω for $$\omega $$ ω even and $$\omega \mapsto d(\omega -1)+1$$ ω ↦ d ( ω - 1 ) + 1 for $$\omega $$ ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ d = 2 .

Abstract. Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.

We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and Nešetřil in the late 1980s, an edge version of the degree--diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this, we obtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving on earlier bounds for this parameter.

We develop an improved bound for the chromatic number of graphs of maximum degree Δ under the assumption that the number of edges spanning any neighbourhood is at most for some fixed 0 < σ < 1. The leading term in the reduction of colours achieved through this bound is best possible as σ → 0. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture. We prove that the strong chromatic index is at most 1.772Δ2 for any graph G with sufficiently large maximum degree Δ. We prove that the chromatic number is at most ⌈0.881(Δ + 1) + 0.119ω⌉ for any graph G with clique number ω and sufficiently large maximum degree Δ. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most (1 – σ) Δ, and establish what may be considered first progress towards a conjecture of Vu.

Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$th power of $G$? For $t\ge 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.

We consider the variation of Ramsey numbers introduced by Erdös and Pach [J. Graph Theory, 7 (1983), pp. 137--147], where instead of seeking complete or independent sets we only seek a $t$-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph. For any $\nu > 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell-1) + \nu$ provided that $G$ has at least $k^{\Omega(\nu^2)}$ vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erdös and J. Pach, J. Graph Theory, 7 (1983), pp. 137--147]. For the above result, we permit $H$ to have order at least $k$. In the harder problem, where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.

A graph G is a k-sphere graph if there are k-dimensional real vectors v 1,…,v n such that ij∈E(G) if and only if the distance between v i and v j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v 1,…,v n such that ij∈E(G) if and only if the dot product of v i and v j is at least 1. By relating these two geometric graph constructions to oriented k-hyperplane arrangements, we prove that the problems of deciding, given a graph G, whether G is a k-sphere or a k-dot product graph are NP-hard for all k>1. In the former case, this proves a conjecture of Breu and Kirkpatrick (Comput. Geom. 9:3–24, 1998). In the latter, this answers a question of Fiduccia et al. (Discrete Math. 181:113–138, 1998). Furthermore, motivated by the question of whether these two recognition problems are in NP, as well as by the implicit graph conjecture, we demonstrate that, for all k>1, there exist k-sphere graphs and k-dot product graphs such that each representation in k-dimensional real vectors needs at least an exponential number of bits to be stored in the memory of a computer. On the other hand, we show that exponentially many bits are always enough. This resolves a question of Spinrad (Efficient Graph Representations, 2003).

We present a linear-time algorithm that, given a planar graph with $m$ edges and maximum degree $3$, finds an induced matching of size at least $m/9$. This is best possible.

A graph G is a k-sphere graph if there are k-dimensional real vectors v1,..., vn such that ij ∈ E(G) if and only if the distance between vi and vj is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v1,...,vn such that ij ∈ E(G) if and only if the dot product of vi and vj is at least 1. By relating these two geometric graph constructions to oriented k-hyperplane arrangements, we prove that the problems of deciding, given a graph G, whether G is a k-sphere or a k-dot product graph are NP-hard for all k>1. In the former case, this proves a conjecture of Breu and Kirkpatrick (1998). In the latter, this answers a question of Fiduccia, Scheinerman, Trenk and Zito (1998).

An edge-face coloring of a plane graph with edge set [Formula: see text] and face set [Formula: see text] is a coloring of the elements of [Formula: see text] such that adjacent or incident elements receive different colors. Borodin [2 2 ] proved that every plane graph of maximum degree [Formula: see text] can be edge-face colored with [Formula: see text] colors. Borodin’s bound was recently extended to the case where [Formula: see text]. In this paper, we extend it to the case [Formula: see text].

Abstract Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is k‐improper if no more than k neighbors of every vertex have the same colour as that assigned to the vertex. The k‐improper chromatic number χk(G) is the least number of colors needed in a k‐improper coloring of a graph G. The main subject of this work is analyzing the complexity of computing χk for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP‐completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing χk for unit interval graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009