Smaller planar triangle-free graphs that are not 3-list-colorable

In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.     

List coloring triangle-free planar graphs

This paper proves the following result. Assume $G$ is a triangle-free planar graph, $X$ is an independent set of $G$. If $L$ is a list assignment of $G$ such that $\text{◂=▸}|L\left(v\right)|=4$ for each vertex $\text{◂+▸}v\in V\left(G\right)-X$ and $\text{◂=▸}|L\left(v\right)|=3$ for each vertex $v\in X$, then $G$ is $L$-colorable.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Adaptable choosability of planar graphs with sparse short cycles

Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle.     

Oriented colourings of graphs with maximum degree three and four

We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colouring. These results improve the best known upper bounds of 11 and 80, respectively.     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

A technique for multicoloring triangle-free hexagonal graphs

In order to avoid interference in cellular telephone networks, sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are allotted disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. We deal with the simpler case of triangle-free subgraphs of the lattice. [Frédéric Havet, Discrete Math. 233 (2001) 1–3] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with colors where ω_d is the maximum demand on a clique in the graph. We give a simpler proof and hope that our techniques can be used to prove the conjecture by [McDiarmid and Reed, Networks Suppl. 36 (2000) 114–117] that these graphs are -multicolorable.     

Colouring random graphs

We discuss some results concerned with the behaviour of colouring algorithms on large random graphs.     

A characterization of projective-planar signed graphs

A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph.     

List colouring of graphs and generalized Dyck paths

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V\left(G\right)\to N$ is a mapping. For a nonnegative integer $m$, let $f^{\left(m\right)}$ be the extension of $f$ to the graph $G$

 $\overline{K_m}$ for which $f^{\left(m\right)}\left(v\right)=\left|V\left(G\right)\right|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-paintable. We study the parameter $m_c(K_n,f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$, an $\overrightarrow{x}$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $a\times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i\le x_{j+1}$. Let $\psi \left(\overrightarrow{x}\right)$ be the number of $\overrightarrow{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $\psi \left((0,1,\dots ,n?1)\right)$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f\left(v_1\right)\le f\left(v_2\right)\le \dots \le f\left(v_n\right)$, then $m_c(G,f)=m_p(G,f)=\psi \left(\overrightarrow{x}\left(f\right)\right)$, where $\overrightarrow{x}\left(f\right)=(x_1,x_2,\dots ,x_n)$ and $x_i=f\left(v_i\right)?i$ for $i=1,2,\dots ,n$. Therefore, if $f\left(v_i\right)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$. We also show that if $G=G_1\cup G_2\cup ?\cup G_p$ is the disjoint union of graphs $G_1,G_2,\dots ,G_p$ and $f=f_1\cup f_2\cup ?\cup f_p$, then $m_c(G,f)={\prod }_{i=1}^p{m}_c(G_i,f_i)$ and $m_p(G,f)={\prod }_{i=1}^p{m}_p(G_i,f_i)$. This generalizes a result in Carraher et al. (2014), where the case each $G_i$ is a copy of $K_1$ is considered.     

Colouring triangle-free intersection graphs of boxes on the plane

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3- and 2-degenerate, respectively. This implies that these graphs are 4- and 3-list-colourable, respectively.     

Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.